Merge sort is a method of sorting based on the divide and conquer technique. It is one of the most respected algorithms, withΟ(n log n)being the worst-case time complexity.
Merge sort divides the list into equal parts, first of all, and then combines them in a sorted way.
Working
We take an unsorted array as the following to comprehend merge sort form.
We know that the merging sort first iteratively splits the entire array into equal halves before the atomic values are reached. Here we see that an array of 8 objects is divided into two 4-size arrays.
The sequence of appearance of objects in the original does not alter this. We are breaking these two arrays into halves now.
We split these arrays further and atomic value is reached, which can no longer be divided.
Now, in just the same way that they were broken down, we merge them. Please notice the colour codes that are given for these lists.
For each list, we first compare the elements and then sort them into another list. We see that there are 14 and 33 in graded positions. Compare 27 and 10 and we put 10 first in the goal list of 2 values, followed by 27. We modify the order of 19 and 35, while 42 and 44 are sequentially positioned.
We compare lists of two data values in the next iteration of the combining process and combine them into a list of found data values, placing them all in a sorted order.
After the final merging, the list should look like this −
Now we should learn some programming aspects of merge sorting.
Algorithm
Pseudocode
