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.

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.

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.

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.