Merge Sort Algorithm

Given an array of integers, sort it using merge sort algorithm.

 

 
Merge sort is an efficient in-place sorting algorithm which produces a stable sort, which means that if two elements have the same value, they holds same relative position in the output as they did in the input. In other words, the relative order of elements with equal values is preserved in the sorted output. Merge sort is a comparison sort which means that it can sort any input for which a less-than relation is defined.

 

How Merge sort works?

 

Merge sort is a divide and conquer algorithm. Like all divide and conquer algorithms, merge sort divides a large array into two smaller subarrays and then recursively sort the subarrays. Basically, there are two steps are involved in whole process –

  1. Divide the unsorted array into n subarrays, each of size 1 (an array of size 1 is considered sorted).
     
  2. Repeatedly merge subarrays to produce new sorted subarrays until only 1 subarray is left which would be our sorted array.

Below diagram shows top-down view of recursive merge sort algorithm used to sort an array of 7 integers.

merge sort steps

 
Below is C implementation of Merge Sort Algorithm:

C

Download   Run Code

Output:

-50 -41 -34 -23 -21 -11 5 9 10 19 26 33 35 40 49

Merge Sort Performance:

 
Worst case time complexity of merge sort is O(nlog(n)). The recurrence relation is

T(n) = 2T(n/2) + cn = O(nlog(n))

The recurrence basically summaries merge sort algorithm – Sort two lists of half the size of the original list, and add the n steps taken to merge the resulting two lists.

Auxiliary space required by it is O(n).

 
Also See:

1. Iterative Mergesort Algorithm

2. External Mergesort

 
References: https://en.wikipedia.org/wiki/Merge_sort

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz