Merge Sort

Given an unsorted array, rearrange it in ascending order. Merge sort splits the array in half, recursively sorts each half, then merges the two sorted halves back together. The merge operation takes O(n) and the recursion depth is O(log n), giving O(n log n) overall.

One Deep Walkthrough: [38, 27, 43, 3, 9, 82, 10]

Step 1 — divide.

Split the array recursively until each subarray has one element:

Step 2 — conquer (merge from bottom up).

Merge [27] and [43]. Both are single elements, so the merge simply picks the smaller first.

Merge [3] and [9] → [3, 9].

Merge [82] and [10] → [10, 82].

Now merge [38] with [27, 43]:

Merge [3, 9] with [10, 82]:

Finally, merge [27, 38, 43] with [3, 9, 10, 82]:

Result: [3, 9, 10, 27, 38, 43, 82].

Code

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

    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])

    return merge(left_half, right_half)


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

Line by line (merge_sort):

• if len(arr) <= 1: return arr — base case. A single element is trivially sorted. The <= 1 (not == 1) also handles an empty array gracefully.
• mid = len(arr) // 2 — split point.
• left_half = merge_sort(arr[:mid]) — recursively sort the left half. The slice creates a new array each time.
• right_half = merge_sort(arr[mid:]) — recursively sort the right half.
• return merge(left_half, right_half) — combine the sorted halves.

Inside merge:

• result = [] — the merged output. The function builds a new array rather than sorting in place.
• i = j = 0 — pointers into left and right respectively.
• while i < len(left) and j < len(right): — run as long as both halves have elements remaining.
• if left[i] <= right[j]: — the left element is smaller (or equal). Pick from left. Using <= (not <) makes the merge stable: equal elements from the left half appear before equal elements from the right half.
• result.append(left[i]); i += 1 — consume the left element.
• else: result.append(right[j]); j += 1 — right element is smaller. Consume it.
• result.extend(left[i:]) — one half is exhausted. Append all remaining elements from the other half. Only one of the two extend calls adds elements; the other appends an empty slice.

Edge case — two elements. [5, 1]. Split into [5] and [1]. Merge: compare 1 < 5 → pick 1, then pick 5. [1, 5].

Time: O(n log n) — always. Best, average, and worst cases are all O(n log n). Space: O(n) — the merge allocates a new array. Additional O(log n) for the recursion stack.

Code Trace

Tracing the final merge call merge([27, 38, 43], [3, 9, 10, 82]):

Merge sort guarantees O(n log n) in every case — the only stable, guaranteed-logarithmic sort here. Quick sort is faster on average, but merge sort has no worst-case pitfalls.

→ LeetCode 912: Sort an Array — merge sort passes comfortably.