Merge Sort
Merge sort (sometimes spelled mergesort) is an efficient sorting algorithm that uses a divideandconquer approach to order elements in an array. Sorting is a key tool for many problems in computer science. For example, inputting a list of names to a sorting algorithm can return them in alphabetical order, or a sorting algorithm can order a list of basketball players by how many points they each scored. Running time is an important thing to consider when selecting a sorting algorithm since efficiency is often thought of in terms of speed. Mergesort runs in a guaranteed \(O(n \log n)\) time, which is significantly faster than the average and worstcase running times of several other sorting algorithms.
Sorting may seem like a simple concept, but efficient sorting is critical when dealing with large amounts of data. Sorting is the basis for more complex computer programs such as searching for files on a computer, finding the shortest route to a destination, and compressing data.
Mergesort
Mergesort has two steps: merging and sorting. The algorithm uses a divideandconquer approach to merge and sort a list.
Divide and conquer is a technique used for breaking algorithms down into subproblems, solving the subproblems, and then combining the results back together to solve the original problem. It can be helpful to think of this method as divide, conquer, and combine.
The mergesort algorithm focuses on how to merge together two presorted arrays such that the resulting array is also sorted. Mergesort can be implemented either recursively or iteratively.
Here is the recursive mergesort algorithm:
 If the list has only one element, return the list and terminate. (base case)
 Split the list into two halves that are as equal in length as possible. (divide)
 Using recursion, sort both lists using mergesort. (conquer)
 Merge the two sorted lists and return the result. (combine)
This animation illustrates the procedure described above.
The Merge Step
The mergesort function uses the merge function. The purpose of the merge function is to merge two sorted lists such that the resulting list is also sorted.
The Merge Algorithm:
Here is one way to implement merge:
 Create an empty list called the result list.
 Do the following until one of the input lists is empty: Remove the first element of the list that has a lesser first element and append it to the result list.
 When one of the lists is empty, append all elements of the other list to the result.
Use the Merge algorithm to find the third step of the merge of A and B. Here are the first two steps.
Initial State  A = [2,4,9]  B = [1,7,13,15]  Results = [ ] 
First Step  A = [2,4,9]  B = [7,13,15]  Results = [1] 
Second Step  A =[4,9]  B = [7,13,15]  Results = [1,2] 
Complexity of Merge:
The merge function does a \(O(1)\) (constant) number of operations for each element in the list. The list size is \(O(n)\) since there are \(n\) elements. Merge does a constant amount of work \(O(n)\) times, so merge runs in \(O(n)\) time.
Mergesort Implementation
Here is one way to implement mergesort in Python. There are many other implementations of the algorithm, but the ideas behind them are the same. Mergesort can be used to sort any orderable list.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 

Complexity of Mergesort
Division:
It takes \(O(1)\) time to divide the problem into two parts. To divide the problem, the algorithm computes the middle of the list by taking the length of the list and dividing by two, which takes constant time.
Solving the subproblems:
Two equally large subproblems are produced. Each half takes \(T\left(\frac{n}{2}\right)\) time, so solving the subproblems takes a total of \(2\,T\left(\frac{n}{2}\right)\) time.
Combining the Subproblems:
This is the merge step of mergesort. This step takes \(O(n)\) time, as shown in the analysis of the merge algorithm.
Therefore, \[ T(n) = 2\,T \left ( \frac{n}{2} \right ) + O(n) .\] The master theorem tells us that the solution to this recurrence is \[T(n) = O(n \log n).\] Mergesort runs in \(O(n \log n)\) time in its best case, worst case, and average case. That means that no matter what the input, mergesort will operate in \(O(n \log n)\) time.
Some other sorting algorithms have a faster bestcase running time, such as insertion sort, which runs at best in \(O(n)\) time. However, insertion sort has a worst and averagecase running time of \(O(n^2)\), which is much slower than \(O(n)\) and \(O(n \lg n)\). You might choose insertion sort over mergesort if your list is already mostly sorted—insertion sort would take \(O(n)\), while mergesort will still take \(O(n \log n)\). Mergesort is used when we want a guaranteed running time of \(O(n \log n)\), regardless of the state of the input.
Mergesort is a stable sort with a space complexity of \(O(n)\).