Merge Sort

So you want to sort your data, but bubble sort is too slow and you don’t have the time to write Timsort. That’s when you decide to write your merge sort algorithm.

What is Merge Sort?

Merge sort is a divide and conquer algorithm that breaks down a list into smaller pieces and eventually pieces them back together one by one sorting the data as it does so.

Steps:

1. Divide:

Split the input array in half, and split each one of those in half, and each half in half, and so on until both halves have only 1 element in each.

2. Conquer:

Merge the array together starting with the last two split arrays and working back to the first split [*hint* recursion].

3. Merge:

To merge each two arrays, start from the first element of each array and add the lower of the two to a new larger sorted array. Then compare the next lowest element in each array that is already not in Since each half is already sorted, this greedy algorithm will allow you to quickly combine the two sorted arrays into a larger sorted array.

Runtime

Both the best and worst case of merge sort is: n log(n).

Merging the elements together takes n time for each level that is merged. Each level of the array is half the size of the level below it, just like in a binary search. Because the problem is cut in half each time, it will take log n levels to get to the top level. Substituting in log n for L gives the runtime of the merge sort n log n.