Merge Sort I

Stable Sort

Like QuickSort, MergeSort runs quickly in O(n log n) time. While Mergesort uses more space and is not usually as fast (in practice) as Quicksort, Mergesort has the benefit of being stable, which means it keeps duplicate elements in the original order that they started with. This is meaningless if the values being sorted is all there is, but usually there's associated data with each element which sometimes needs to be preserved in the original order. For example, if you sort by one value of an item, and then by another value, you may not want the second sort to mess up the order of the first sort.

Stable Sort Example

Challenge:
Sort a deck of card so the suits are in order and each suit is in number-order.

Answer:

0 - Start with an unsorted deck
1 - Sort the entire deck by number
2 - Use a stable sort and sort by suit. Since the sort is stable, the number order is preserved. See each step below:

Wikipedia

Merge Method

The main part of MergeSort involves the merge method, which merges 2 sorted arrays to create one sorted array. This can be done in one pass through the arrays, by comparing the values of the two arrays before placing a value in the large array.

Challenge

You are given an array, where each half is sorted. Can you merge the two halves and print the sorted array? This should be done with only one run through the array.