Merge sort

Merge sort is a divide and conquer algorithm that has a lower order running time than the insertion sort. The merge sort algorithm works by using recursion; it will repeatedly divide an unsorted list into two halves. When the list has a single item or it is empty it is considered sorted; this is called the base case. The majority of the sorting work is performed in the merge function, which is responsible for combining the two halves back together. The merge function uses a temporary array of equal size to the input array during the merge process so it has a higher order auxiliary space of O(n). Because of this, merge sort is generally better off implemented for sorting a linked list instead of an array. We'll look at both implementations so you can see the performance differences based on the dataset size.

The algorithm for array-based merge sort

There are three steps to the divide and conquer process for sorting a collection. They are:

• Divide: If the collection S is zero or one...