Merge Sort

Definition

Merge sort is a divide-and-conquer algorithm that splits the array in halves, sorts each and merges them.

Guaranteed O(n log n) and stable — used for linked lists and external sorting.

Diagram

Flowchart

Example: Merge sort in Python

def ms(a):
    if len(a) <= 1:
        return a
    m = len(a) // 2
    l, r = ms(a[:m]), ms(a[m:])
    out, i, j = [], 0, 0
    while i < len(l) and j < len(r):
        if l[i] <= r[j]:
            out.append(l[i]); i += 1
        else:
            out.append(r[j]); j += 1
    return out + l[i:] + r[j:]
print(ms([5, 2, 4, 1]))

Output: [1, 2, 4, 5]

Complexity

Time O(n log n) · Space O(n)

Key points

• Stable sort
• Not in-place
• Basis for counting inversions

Interview questions

More DSA topics