Merge Sort

Merge sort (sometimes spelled mergesort) is an efficient sorting algorithm that uses a divide-and-conquer 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 worst-case 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 has two steps: merging and sorting. The algorithm uses a divide-and-conquer 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 pre-sorted arrays such that the resulting array is also sorted. Mergesort can be implemented either recursively or iteratively.

Here is the recursive mergesort algorithm:

1. If the list has only one element, return the list and terminate. (Base case)
2. Split the list into two halves that are as equal in length as possible. (Divide)
3. Using recursion, sort both lists using mergesort. (Conquer)
4. Merge the two sorted lists and return the result. (Combine)

This animation illustrates the procedure described above.

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:

1. Create an empty list called the result list.
2. 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.
3. When one of the lists is empty, append all elements of the other list to the result.

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.

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

def merge(left, right):
    result = []
    left_idx, right_idx = 0, 0
    while left_idx < len(left) and right_idx < len(right):
        # change the direction of this comparison to change the direction of the sort
        if left[left_idx] <= right[right_idx]:
            result.append(left[left_idx])
            left_idx += 1
        else:
            result.append(right[right_idx])
            right_idx += 1

    if left:
        result.extend(left[left_idx:])
    if right:
        result.extend(right[right_idx:])
    return result

def merge_sort(m):
    if len(m) <= 1:
        return m

    middle = len(m) // 2
    left = m[:middle]
    right = m[middle:]

    left = merge_sort(left)
    right = merge_sort(right)
    return list(merge(left, right))

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 best-case running time, such as insertion sort, which runs at best in \(O(n)\) time. However, insertion sort has a worst- and average-case running time of \(O(n^2)\), which is much slower than \(O(n)\) and \(O(n \log 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)\).

Pros

• Time-efficient with time complexity of \(O(n \log n)\)
• Can be used for external sorting
• Highly parallelizable
• Stable sort

Cons

• Marginally slower than quicksort in practice
• Not as space-efficient as other sorting algorithms, e.g. block sort