Implementation

Merge sort and quicksort in Python, explained line by line, then the same merge sort in C++, Java and TypeScript.

Merge sort in Python

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


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


print(merge_sort([38, 27, 43, 3, 9, 82, 10]))  # [3, 9, 10, 27, 38, 43, 82]

• len(items) <= 1: the base case. items[:] returns a copy, so the input is never modified.
• mid = len(items) // 2: split in the middle and sort each half recursively.
• The merge loop appends the smaller of the two front elements.
• left[i] <= right[j]: on ties the left element goes first, which makes the sort stable. Using < would break stability.
• extend: when one side runs out, the sorted rest of the other is appended.

Every slice allocates a new list; faster versions reuse one buffer and index ranges, as in C++ and Java below.

Quicksort in Python

import random


def quicksort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    while lo < hi:
        lt, gt = partition3(a, lo, hi)
        if lt - lo < hi - gt:          # recurse on the smaller side only
            quicksort(a, lo, lt - 1)
            lo = gt + 1
        else:
            quicksort(a, gt + 1, hi)
            hi = lt - 1


def partition3(a, lo, hi):
    pivot = a[random.randint(lo, hi)]
    lt, i, gt = lo, lo, hi
    while i <= gt:
        if a[i] < pivot:
            a[lt], a[i] = a[i], a[lt]
            lt += 1
            i += 1
        elif a[i] > pivot:
            a[i], a[gt] = a[gt], a[i]
            gt -= 1
        else:
            i += 1
    return lt, gt


data = [5, 2, 8, 2, 9, 1, 5, 5]
quicksort(data)
print(data)  # [1, 2, 2, 5, 5, 5, 8, 9]

• random.randint(lo, hi): a random pivot makes the O(n²) case unlikely on any input, including sorted data.
• partition3: a three-way partition (the Dutch national flag problem). Afterwards a[lo:lt] is smaller than the pivot, a[lt:gt+1] equals it and a[gt+1:hi+1] is larger. Equal keys are never revisited, so duplicates stay fast.
• In the a[i] > pivot branch i does not advance, because the value swapped in from a[gt] has not been examined yet.
• while lo < hi plus recursing on the smaller side caps recursion depth at O(log n), well below Python's default limit of 1000.

Merge sort in C++

#include <cstddef>
#include <iostream>
#include <vector>

template <typename T>
void merge_sort(std::vector<T>& a, std::vector<T>& buf, std::size_t lo, std::size_t hi) {
    if (hi - lo <= 1) return;                 // half-open range [lo, hi)
    std::size_t mid = lo + (hi - lo) / 2;
    merge_sort(a, buf, lo, mid);
    merge_sort(a, buf, mid, hi);
    std::size_t i = lo, j = mid, k = lo;
    while (i < mid && j < hi) {
        if (a[j] < a[i]) buf[k++] = a[j++];   // right only if strictly smaller: stable
        else buf[k++] = a[i++];
    }
    while (i < mid) buf[k++] = a[i++];
    while (j < hi) buf[k++] = a[j++];
    for (std::size_t t = lo; t < hi; ++t) a[t] = buf[t];
}

template <typename T>
void merge_sort(std::vector<T>& a) {
    std::vector<T> buf(a.size());
    merge_sort(a, buf, 0, a.size());
}

int main() {
    std::vector<int> v{38, 27, 43, 3, 9, 82, 10};
    merge_sort(v);
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';
}

One buffer, half-open ranges, and only operator<. In production code, std::stable_sort does this job.

Merge sort in Java

import java.util.Arrays;

public class MergeSort {
    public static void sort(int[] a) {
        int[] buf = new int[a.length];
        sort(a, buf, 0, a.length);
    }

    private static void sort(int[] a, int[] buf, int lo, int hi) {
        if (hi - lo <= 1) return;
        int mid = lo + (hi - lo) / 2;          // no (lo + hi) overflow
        sort(a, buf, lo, mid);
        sort(a, buf, mid, hi);
        int i = lo, j = mid, k = lo;
        while (i < mid && j < hi) {
            buf[k++] = (a[j] < a[i]) ? a[j++] : a[i++];
        }
        while (i < mid) buf[k++] = a[i++];
        while (j < hi) buf[k++] = a[j++];
        System.arraycopy(buf, lo, a, lo, hi - lo);
    }

    public static void main(String[] args) {
        int[] v = {38, 27, 43, 3, 9, 82, 10};
        sort(v);
        System.out.println(Arrays.toString(v));
    }
}

System.arraycopy copies the merged range back. For objects, take a Comparator<? super T> and test c.compare(a[j], a[i]) < 0.

Merge sort in TypeScript

function mergeSort<T>(items: readonly T[], compare: (a: T, b: T) => number): T[] {
  if (items.length <= 1) return items.slice();
  const mid = Math.floor(items.length / 2);
  const left = mergeSort(items.slice(0, mid), compare);
  const right = mergeSort(items.slice(mid), compare);
  const merged: T[] = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    if (compare(right[j], left[i]) < 0) merged.push(right[j++]);
    else merged.push(left[i++]);
  }
  while (i < left.length) merged.push(left[i++]);
  while (j < right.length) merged.push(right[j++]);
  return merged;
}

console.log(mergeSort([38, 27, 43, 3, 9, 82, 10], (a, b) => a - b));

The comparator follows the Array.prototype.sort contract (negative means a first), and T makes it generic.

Summary

• Merge sort stays stable thanks to one detail: on ties, take from the left.
• Random pivots, three-way partitioning and smaller-side recursion make quicksort robust.
• Across languages the core is identical: one reusable buffer and half-open ranges.