Merge Sort Algorithm

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

 

 
Merge sort is an efficient sorting algorithm which produces a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Mergesort is a comparison sort, i.e. it can sort items of any type for which a less-than relation is defined. Merge sort’s most common implementation does not sort in-place.

 

How Mergesort works?

 
Mergesort is a divide and conquer algorithm. Like all divide and conquer algorithms, mergesort first divides a large array into two smaller sub-arrays and then recursively sort the sub-arrays. Basically, there are two steps are involved in whole process –

  1. Divide the unsorted array into n sub-arrays, each containing 1 element (a array of 1 element is considered sorted).
     
  2. Repeatedly merge sub-arrays to produce new sorted sub-arrays until there is only 1 sub-array remaining. This will be the sorted array.

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

  merge-sort-steps

C++

Download   Run Code

Output:

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

Performance:

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

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

The recurrence basically summaries mergesort – 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).

 

 
 
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