Kata: Merge Sort

Table of contents

Problem Statement

Implement merge sort:

1. Divide: Split the array into two halves
2. Conquer: Recursively sort each half
3. Combine: Merge the two sorted halves

Also implement a merge function that merges two sorted arrays into one sorted array.

Concepts

Merge sort is the canonical divide-and-conquer algorithm. It guarantees O(n log n) time in all cases (best, average, worst), unlike quicksort which degrades to O(n^2) in the worst case.

Trade-off: Merge sort uses O(n) extra space, while quicksort sorts in place (O(log n) stack space).

Python: Python’s built-in sorted() and list.sort() use Timsort, a hybrid of merge sort and insertion sort. See Python Core Concepts.

Boilerplate

TypeScript

// merge-sort.ts
function merge<T>(left: T[], right: T[]): T[] {
  // TODO: merge two sorted arrays
  return [];
}

function mergeSort<T>(arr: T[]): T[] {
  // TODO: divide and conquer
  return [];
}

Hints

Solution

TypeScript

function merge<T>(left: T[], right: T[]): T[] {
  const result: T[] = [];
  let i = 0;
  let j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  return [...result, ...left.slice(i), ...right.slice(j)];
}

function mergeSort<T>(arr: T[]): T[] {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

Python

def merge(left: list, right: list) -> list:
    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

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

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

PHP

function merge(array $left, array $right): array {
    $result = [];
    $i = $j = 0;

    while ($i < count($left) && $j < count($right)) {
        if ($left[$i] <= $right[$j]) {
            $result[] = $left[$i++];
        } else {
            $result[] = $right[$j++];
        }
    }

    return array_merge($result, array_slice($left, $i), array_slice($right, $j));
}

function mergeSort(array $arr): array {
    if (count($arr) <= 1) return $arr;

    $mid = intdiv(count($arr), 2);
    $left = mergeSort(array_slice($arr, 0, $mid));
    $right = mergeSort(array_slice($arr, $mid));

    return merge($left, $right);
}

Complexity Analysis

Why O(n log n)? The array is divided log n times (halving each time). At each level, merging all elements takes O(n). So total = O(n) * O(log n) = O(n log n).

Comparison with Other Sorts

Cross-Language Notes

Python: Python’s Timsort (used by sorted() and .sort()) is a hybrid merge sort + insertion sort that exploits existing order in the data. It achieves O(n) best case for nearly-sorted arrays. In production, always use the built-in sort.

PHP: sort(), usort(), and related functions use an introsort variant (quicksort + heapsort fallback). For stable sorting, use array_multisort() or implement merge sort.

JavaScript/TypeScript: V8’s Array.prototype.sort() uses Timsort since 2019. It’s stable as of ES2019 specification.

Fun fact: Merge sort is the preferred algorithm for sorting linked lists, where random access is O(n) but sequential access is O(1). Quicksort’s advantage (in-place, cache-friendly) disappears with linked lists.