Learn Computer Science

Merge Sort

Tutoring > Data Structures > Merge Sort

Merge sort is O(n log n) for each case. It is a divide and conquer algorthim invented by John Von Neumann in 1945.

 

• It is performed by dividing the input array into 1-element sized sub-arrays.

• These are then paired up with the elements in order. For example, if a 3 was paired with a 1, the new sub-array would be {1, 3}

• These new sub-arrays are then paired up again and sorted.

• This repeats until the sub-arrays have all been joined together. The resulting array will be sorted.

 

1   2   3   4   5   6   7   8   9   - this is the sorted array.

1   2   3   4   5   7   8   9 |  6   - the sub-arrays are combined again.

2   3   4   7 | 1   5    8   9 | 6   - the sub- arrays are combined again.

3   4 | 2   7 | 1   8 | 5   9 | 6   - the elements are paired up in their sorted order.

4   3   2   7    8   1   9   5   6   - this is the array we start wth, un-sorted.

 

There are many different ways to merge the elements, the above example is a simple one called a bottom-up implementation. You can also preform a top-down and natural implementations.