How does merge sort work?

Merge sort

Merge sort is a kind of sorting technique which based on divide and conquer algorithm in computer programming. It is one of the most popular sorting algorithms and a great way to develop confidence in building recursive algorithms, and it is one of the most respected algorithms in worst-case time complexity being Ο(n log n). If the running time of merge sort for a list of length n is T(n), then the recurrence T(n) = 2T(n/2) + n.

Merging is the process of taking two smaller sorted lists and combining them together into a single, sorted, new list. In this key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.

Logic

function merge(left,right)
   var list result
   while length(left) > 0 or length(right) > 0
       if length(left) > 0 and length(right) > 0
           if first(left) <= first(right)
               append first(left) to result
               left = rest(left)
           else
               append first(right) to result
               right = rest(right)
       else if length(left) > 0
           append first(left) to result
           left = rest(left)             
       else if length(right) > 0
           append first(right) to result
           right = rest(right)
   end while
   return result

Divide and Conquer process in merge sort

By using the Divide and Conquer technique, we divide a problem into subproblems. Then we combine the results from the subproblem when each subproblem is ready after that will solve the main problem.

Suppose we had to sort an array C. C subproblem would be to sort a sub-section of this array starting at index m and ending at index o, denoted as c[m..o].

Divide

If n is the half-way point between m and o, then we can split the subarray C[m..o] into two arrays C[m..n] and C[n+1, o].

Conquer

The next conquer step, we try to sort both the subarrays C[m..n] and C[n+1, o]. If we haven't yet reached the base case, we again divide both these subarrays and try to sort them.

Combine

When the conquer step reaches the base step and we get two sorted subarrays C[m..n] and C[n+1, o] for array C[m..o], we combine the results by creating a sorted array C[m..o] from two sorted subarrays C[m..n] and C[n+1, o].

As we already mention that merge sort first divides the array into equal halves and then combines them in a sorted manner.

Now let’s see how merge sort works through an example

To understand merge sort process, we take an unsorted array as the following −

First, merge sort divides the whole array iteratively into equal halves unless the atomic values are achieved. Here, an array of 8 items is divided into two arrays with four contain in each.

This does not change the sequence of appearance of items in the original. Now we divide above two arrays into halves.

In next step, we divide the arrays and we achieve undivided atomic value.

Then, we combine them in the same manner as they broke down.

After that, we compare the element for each list and then combine them into another list in a sorted manner. That 18 and 35 are in sorted positions. And compare 22 and 15 and in the target list of two values we put 15 first, and then 22. We change the order of 19 and 38 whereas 46 and 48 are placed sequentially.

Next iteration of the combining phase, we compare lists of two data values and merge them into a list of found data values placing all in a sorted order.

After the final merging, the list should look like this −

Finally, we learn some programming aspects of merge sorting.

Performance

Worst case - O(n log n)

Best-case - O(n log n) typical, O(n) natural variant

Average case - O(n log n)

Worst-case space complexity - О(n) total with O(n) auxiliary, O(1) auxiliary with linked lists

Applications of Merge Sort

• Merge Sort is useful for sorting linked lists in O(nLogn) time.

• Used In inversion Count Problem

• Used in External Sorting

Merge sort implementation in different programming languages

Merge Sort in C

Merge Sort in C++

Merge Sort in JAVA

Merge Sort in Python