Merge Sort Algorithm

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


Merge sort is an efficient, general-purpose 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 list into n sublists, each containing 1 element (a list of 1 element is considered sorted).

2. Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

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


C++ implementation –

Download   Run Code


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



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).


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