Merge Sort

Merge sort divides the input into smaller parts, sorts each part, and merges the sorted results. It is a clear example of divide and conquer.

Its usual time complexity is O(n log n).

Core Idea

The algorithm keeps splitting the array until the pieces are trivially sorted. Then it merges two sorted lists by repeatedly taking the smaller front value.

Merge sort is predictable because the input is divided in half regardless of the original order.

The work has two layers: recursive splitting and merging. Splitting creates smaller problems. Merging is where sorted pieces become a larger sorted piece.

Function Contract

merge(left, right) expects two already sorted lists and returns one new sorted list containing all their elements.

merge_sort(values) expects a list of comparable values and returns a new sorted list. The clarity-first implementation uses slices, so it does not sort the original list in place.

Python Example

def merge(left, right):
    result = []
    i = j = 0
 
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
 
    result.extend(left[i:])
    result.extend(right[j:])
    return result

The merge step is linear in the total length of the two lists.

Full Implementation

def merge_sort(values):
    if len(values) <= 1:
        return values
 
    mid = len(values) // 2
    left = merge_sort(values[:mid])
    right = merge_sort(values[mid:])
 
    return merge(left, right)

This clarity-first version returns a new sorted list. The slices also create new lists, which matters for space usage.

Step-by-Step Example

For [4, 1, 3, 2], merge sort splits into [4, 1] and [3, 2], then into single-element lists. Single-element lists are already sorted.

Then it merges:

[4] and [1] -> [1, 4]
[3] and [2] -> [2, 3]
[1, 4] and [2, 3] -> [1, 2, 3, 4]

Why It Works

The base case is sorted because a list of length zero or one cannot be out of order. The recursive calls sort the left and right halves. The merge step preserves sorted order because it repeatedly chooses the smaller front value from two already sorted lists.

By induction, every returned list is sorted.

Complexity

There are O(log n) levels of splitting. At each level, the merge work across all pieces is O(n). The time complexity is O(n log n). The simple version uses O(n) or more extra space depending on slicing and implementation details.

Common Confusions

The merge step is not sorting from scratch. It relies on both inputs already being sorted.

Merge sort often uses extra memory for temporary arrays. That space cost matters when comparing it with in-place sorting strategies.

Another common confusion is thinking the split order depends on values. Merge sort splits by position, not by comparing values.

When To Use It

Use merge sort to understand divide and conquer, stable sorting, predictable O(n log n) behavior, and problems where sorted halves can be combined.

In Python practice, use built-in sorting for real sorting tasks. Study merge sort to understand divide and conquer and merging.

The Main Point

Merge sort works by sorting smaller halves and merging already sorted results. The merge step is the mechanism that turns independent sorted pieces into a sorted whole.