ReslandDSA Study Center

Sorting

Learn how merge sort and quicksort trade off, what your library sort guarantees, and when a partition or a custom comparator is the whole answer.

IntermediateRead first: Recursion, Big-O & Complexity

How It Works

Most of the time you sort with the library and move on. An O(n log n) sort is often the cheapest way to make a problem easy: it puts duplicates side by side, lets two pointers and binary search work, and lines up overlapping intervals. No sort that only compares elements can beat O(n log n) in the worst case. Still, you should know how the two classic ones work, because their core moves, merging and partitioning, solve problems of their own.

Both are divide and conquer. Merge sort splits the array in half without looking at the values, sorts each half, and does the real work when it merges the two sorted halves. Quicksort does the work first: it partitions the array around a pivot (smaller values to the left, the rest to the right) and then sorts each side. Nothing needs merging afterward, because every value on the left is already smaller than every value on the right.

merge sort
 [5, 2, 4, 6, 1, 3]
 [5, 2, 4] [6, 1, 3]  split in half
 [2, 4, 5] [1, 3, 6]  sort each half
 [1, 2, 3, 4, 5, 6]   merge

quicksort
 [5, 2, 4, 6, 1, 3]   pivot = nums[2] = 4
 [2, 3, 1] 4 [5, 6]   partition: < 4 left, the rest right
 [1, 2, 3] 4 [5, 6]   sort each side
Merge sort sorts first and combines last. Quicksort splits by value first, so there's nothing left to combine.

Quicksort, Step by Step

Step 1 of 15

nums

  • Pivot
  • Being checked or swapped
  • In its final place
  • Outside the current range

Quicksort [5, 2, 4, 6, 1, 3]. First partition it around a pivot, the middle value: nums[2] = 4.

All 15 steps as text
  1. Quicksort [5, 2, 4, 6, 1, 3]. First partition it around a pivot, the middle value: nums[2] = 4.
  2. Swap the pivot to the end, out of the sweep's way. store = 0 marks where the next value below 4 goes.
  3. 5 isn't below the pivot 4, so leave it for the right side. store stays at 0.
  4. 2 < 4, so swap it into store (index 0) and advance store to 1. Everything left of store is below the pivot.
  5. 3 < 4, so swap it into store (index 1) and advance store to 2. Everything left of store is below the pivot.
  6. 6 isn't below the pivot 4, so leave it for the right side. store stays at 2.
  7. 1 < 4, so swap it into store (index 2) and advance store to 3. Everything left of store is below the pivot.
  8. Swap the pivot into store. The 3 values below 4 are left of index 3 and the rest are right of it, so 4 is in its final place.
  9. Recurse on the left side of 4, [2, 3, 1]. Its middle value, 3, is the pivot.
  10. The partition puts 3 at index 2 with the 2 smaller values to its left. That's its final place.
  11. Recurse on the left side of 3, [2, 1]. Its middle value, 2, is the pivot.
  12. The partition puts 2 at index 1 with the smaller value to its left. That's its final place. 1 is alone on its side, so it's already sorted.
  13. Recurse on the right side of 4, [5, 6]. Its middle value, 5, is the pivot.
  14. Nothing in its range is below 5, so it stays at the front, index 4. That's its final place. 6 is alone on its side, so it's already sorted.
  15. Every value has been a pivot or sat alone in its range, so [1, 2, 3, 4, 5, 6] is sorted. Nothing needs merging, because each partition already split the values in order.
  • Worst case. Merge sort is O(n log n) on every input. Quicksort averages O(n log n) but falls to O(n²) when the pivot keeps landing at one end, as it does on sorted input if you always pick the first or last element. A middle pivot handles sorted input, and a random pivot makes the worst case vanishingly unlikely on any input.
  • Extra space. Merge sort needs O(n) to merge into. Quicksort works in place and only uses its recursion stack: O(log n) on average, O(n) in the worst case.
  • Stability. A stable sort keeps equal elements in their original order, which matters when you sort records by one field and then another. Merge sort is stable as long as the merge takes from the left half on ties. Quicksort isn't, because partitioning swaps elements over long distances.
  • Duplicates. A two-way partition like the one in the template degrades toward O(n²) when many values are equal, since they all land on one side. A three-way partition (less than, equal to, greater than the pivot) fixes that, and it's exactly the trick in Sort Colors below.

When to Reach for It

  • Sorting first would put duplicates, pairs or overlaps next to each other, and O(n log n) fits the budget.
  • The answer is an ordering by some rule other than plain numeric order, which calls for a custom comparator.
  • You need to group values into a few categories in place, in one pass.
  • Equal elements must keep their original order, so you need a stable sort.
  • The values are small integers in a known range, so counting them beats comparing them.

Complexity

OperationTimeSpace
Merge sortO(n log n)O(n)
QuicksortO(n log n) average, O(n²) worstO(log n) average stack, O(n) worst
Counting sort (integers in a range of size k)O(n + k)O(k)

The Template

Merge Sort and Quicksort

mergeSort returns a new sorted array. An array of 0 or 1 elements is already sorted. Anything longer is cut in half, each half is sorted recursively, and merge walks the two sorted halves with one index each, always taking the smaller front value. Taking from the left on ties (<=) is what keeps it stable.

quickSort sorts in place. partition uses the Lomuto scheme. It swaps the middle element to the end to use as the pivot, then sweeps the range with store marking where the next value smaller than the pivot goes. A final swap puts the pivot between the two groups. That's the exact index it will have in the sorted array, so the recursion never touches it again.

Time O(n log n), quicksort O(n²) worst caseSpace O(n) merge sort, quicksort stack O(log n) average and O(n) worst

def merge_sort(nums: list[int]) -> list[int]:
    """Returns a new sorted list. Stable: equal values keep their original order."""
    if len(nums) <= 1:
        return nums[:]  # Already sorted.
    mid = len(nums) // 2
    return merge(merge_sort(nums[:mid]), merge_sort(nums[mid:]))


def merge(left: list[int], right: list[int]) -> list[int]:
    """Merges two sorted lists into one sorted list."""
    merged: list[int] = []
    i = j = 0
    while i < len(left) and j < len(right):
        # <= takes from the left on ties, which is what keeps the sort stable.
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    # One side ran out. What's left of the other is already sorted.
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged


def quick_sort(nums: list[int]) -> None:
    """Sorts `nums` in place. Not stable."""
    quick_sort_range(nums, 0, len(nums) - 1)


def quick_sort_range(nums: list[int], lo: int, hi: int) -> None:
    if lo >= hi:
        return  # 0 or 1 elements: already sorted.
    p = partition(nums, lo, hi)
    # The pivot is in its final place. Sort each side of it.
    quick_sort_range(nums, lo, p - 1)
    quick_sort_range(nums, p + 1, hi)


def partition(nums: list[int], lo: int, hi: int) -> int:
    """Lomuto partition of nums[lo..hi] around its middle element. Smaller values
    end up left of the pivot, the rest right. Returns the pivot's final index."""
    mid = lo + (hi - lo) // 2
    nums[mid], nums[hi] = nums[hi], nums[mid]  # Park the pivot at the end.
    pivot = nums[hi]
    store = lo  # nums[lo..store - 1] are all smaller than the pivot.
    for i in range(lo, hi):
        if nums[i] < pivot:
            nums[i], nums[store] = nums[store], nums[i]
            store += 1
    nums[store], nums[hi] = nums[hi], nums[store]  # Put the pivot between the groups.
    return store


if __name__ == "__main__":
    a = [5, 2, 3, 1]
    b = [5, 1, 1, 2, 0, 0]
    print(merge_sort(a))  # [1, 2, 3, 5]
    print(merge_sort(b))  # [0, 0, 1, 1, 2, 5]
    quick_sort(a)
    quick_sort(b)
    print(a)  # [1, 2, 3, 5]
    print(b)  # [0, 0, 1, 1, 2, 5]
// Returns a new sorted array. Stable: equal values keep their original order.
export function mergeSort(nums: number[]): number[] {
  if (nums.length <= 1) return nums.slice(); // Already sorted.
  const mid = Math.floor(nums.length / 2);
  return merge(mergeSort(nums.slice(0, mid)), mergeSort(nums.slice(mid)));
}

// Merges two sorted arrays into one sorted array.
function merge(left: number[], right: number[]): number[] {
  const merged: number[] = [];
  let i = 0;
  let j = 0;
  while (i < left.length && j < right.length) {
    // <= takes from the left on ties, which is what keeps the sort stable.
    if (left[i] <= right[j]) merged.push(left[i++]);
    else merged.push(right[j++]);
  }
  // One side ran out. What's left of the other is already sorted.
  while (i < left.length) merged.push(left[i++]);
  while (j < right.length) merged.push(right[j++]);
  return merged;
}

// Sorts `nums` in place. Not stable.
export function quickSort(nums: number[]): void {
  quickSortRange(nums, 0, nums.length - 1);
}

function quickSortRange(nums: number[], lo: number, hi: number): void {
  if (lo >= hi) return; // 0 or 1 elements: already sorted.
  const p = partition(nums, lo, hi);
  // The pivot is in its final place. Sort each side of it.
  quickSortRange(nums, lo, p - 1);
  quickSortRange(nums, p + 1, hi);
}

// Lomuto partition of nums[lo..hi] around its middle element. Smaller values
// end up left of the pivot, the rest right. Returns the pivot's final index.
function partition(nums: number[], lo: number, hi: number): number {
  const mid = lo + Math.floor((hi - lo) / 2);
  [nums[mid], nums[hi]] = [nums[hi], nums[mid]]; // Park the pivot at the end.
  const pivot = nums[hi];
  let store = lo; // nums[lo..store - 1] are all smaller than the pivot.
  for (let i = lo; i < hi; i++) {
    if (nums[i] < pivot) {
      [nums[i], nums[store]] = [nums[store], nums[i]];
      store++;
    }
  }
  [nums[store], nums[hi]] = [nums[hi], nums[store]]; // Put the pivot between the groups.
  return store;
}

const a = [5, 2, 3, 1];
const b = [5, 1, 1, 2, 0, 0];
console.log(JSON.stringify(mergeSort(a))); // [1,2,3,5]
console.log(JSON.stringify(mergeSort(b))); // [0,0,1,1,2,5]
quickSort(a);
quickSort(b);
console.log(JSON.stringify(a)); // [1,2,3,5]
console.log(JSON.stringify(b)); // [0,0,1,1,2,5]
package main

import (
	"fmt"
	"slices"
)

// mergeSort returns a new sorted slice. It's stable: equal values keep their
// original order.
func mergeSort(nums []int) []int {
	if len(nums) <= 1 {
		return slices.Clone(nums) // Already sorted.
	}
	mid := len(nums) / 2
	return merge(mergeSort(nums[:mid]), mergeSort(nums[mid:]))
}

// merge combines two sorted slices into one sorted slice.
func merge(left, right []int) []int {
	merged := make([]int, 0, len(left)+len(right))
	i, j := 0, 0
	for i < len(left) && j < len(right) {
		// <= takes from the left on ties, which is what keeps the sort stable.
		if left[i] <= right[j] {
			merged = append(merged, left[i])
			i++
		} else {
			merged = append(merged, right[j])
			j++
		}
	}
	// One side ran out. What's left of the other is already sorted.
	merged = append(merged, left[i:]...)
	return append(merged, right[j:]...)
}

// quickSort sorts nums in place. It isn't stable.
func quickSort(nums []int) {
	quickSortRange(nums, 0, len(nums)-1)
}

func quickSortRange(nums []int, lo, hi int) {
	if lo >= hi {
		return // 0 or 1 elements: already sorted.
	}
	p := partition(nums, lo, hi)
	// The pivot is in its final place. Sort each side of it.
	quickSortRange(nums, lo, p-1)
	quickSortRange(nums, p+1, hi)
}

// partition is a Lomuto partition of nums[lo..hi] around its middle element.
// Smaller values end up left of the pivot, the rest right. It returns the
// pivot's final index.
func partition(nums []int, lo, hi int) int {
	mid := lo + (hi-lo)/2
	nums[mid], nums[hi] = nums[hi], nums[mid] // Park the pivot at the end.
	pivot := nums[hi]
	store := lo // nums[lo..store - 1] are all smaller than the pivot.
	for i := lo; i < hi; i++ {
		if nums[i] < pivot {
			nums[i], nums[store] = nums[store], nums[i]
			store++
		}
	}
	nums[store], nums[hi] = nums[hi], nums[store] // Put the pivot between the groups.
	return store
}

func main() {
	a := []int{5, 2, 3, 1}
	b := []int{5, 1, 1, 2, 0, 0}
	fmt.Println(mergeSort(a)) // [1 2 3 5]
	fmt.Println(mergeSort(b)) // [0 0 1 1 2 5]
	quickSort(a)
	quickSort(b)
	fmt.Println(a) // [1 2 3 5]
	fmt.Println(b) // [0 0 1 1 2 5]
}
using System;

public class Solution
{
    // Returns a new sorted array. Stable: equal values keep their original order.
    public static int[] MergeSort(int[] nums)
    {
        if (nums.Length <= 1) return (int[])nums.Clone(); // Already sorted.
        int mid = nums.Length / 2;
        return Merge(MergeSort(nums[..mid]), MergeSort(nums[mid..]));
    }

    // Merges two sorted arrays into one sorted array.
    static int[] Merge(int[] left, int[] right)
    {
        var merged = new int[left.Length + right.Length];
        int i = 0, j = 0, k = 0;
        while (i < left.Length && j < right.Length)
        {
            // <= takes from the left on ties, which is what keeps the sort stable.
            if (left[i] <= right[j]) merged[k++] = left[i++];
            else merged[k++] = right[j++];
        }
        // One side ran out. What's left of the other is already sorted.
        while (i < left.Length) merged[k++] = left[i++];
        while (j < right.Length) merged[k++] = right[j++];
        return merged;
    }

    // Sorts nums in place. Not stable.
    public static void QuickSort(int[] nums)
    {
        QuickSortRange(nums, 0, nums.Length - 1);
    }

    static void QuickSortRange(int[] nums, int lo, int hi)
    {
        if (lo >= hi) return; // 0 or 1 elements: already sorted.
        int p = Partition(nums, lo, hi);
        // The pivot is in its final place. Sort each side of it.
        QuickSortRange(nums, lo, p - 1);
        QuickSortRange(nums, p + 1, hi);
    }

    // Lomuto partition of nums[lo..hi] around its middle element. Smaller values
    // end up left of the pivot, the rest right. Returns the pivot's final index.
    static int Partition(int[] nums, int lo, int hi)
    {
        int mid = lo + (hi - lo) / 2;
        (nums[mid], nums[hi]) = (nums[hi], nums[mid]); // Park the pivot at the end.
        int pivot = nums[hi];
        int store = lo; // nums[lo..store - 1] are all smaller than the pivot.
        for (int i = lo; i < hi; i++)
        {
            if (nums[i] < pivot)
            {
                (nums[i], nums[store]) = (nums[store], nums[i]);
                store++;
            }
        }
        (nums[store], nums[hi]) = (nums[hi], nums[store]); // Put the pivot between the groups.
        return store;
    }

    public static void Main()
    {
        int[] a = { 5, 2, 3, 1 };
        int[] b = { 5, 1, 1, 2, 0, 0 };
        Console.WriteLine(Format(MergeSort(a))); // [1, 2, 3, 5]
        Console.WriteLine(Format(MergeSort(b))); // [0, 0, 1, 1, 2, 5]
        QuickSort(a);
        QuickSort(b);
        Console.WriteLine(Format(a)); // [1, 2, 3, 5]
        Console.WriteLine(Format(b)); // [0, 0, 1, 1, 2, 5]
    }

    static string Format(int[] values) => "[" + string.Join(", ", values) + "]";
}
import java.util.Arrays;

public class Solution {
    // Returns a new sorted array. Stable: equal values keep their original order.
    static int[] mergeSort(int[] nums) {
        if (nums.length <= 1) return nums.clone(); // Already sorted.
        int mid = nums.length / 2;
        int[] left = mergeSort(Arrays.copyOfRange(nums, 0, mid));
        int[] right = mergeSort(Arrays.copyOfRange(nums, mid, nums.length));
        return merge(left, right);
    }

    // Merges two sorted arrays into one sorted array.
    static int[] merge(int[] left, int[] right) {
        int[] merged = new int[left.length + right.length];
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            // <= takes from the left on ties, which is what keeps the sort stable.
            if (left[i] <= right[j]) merged[k++] = left[i++];
            else merged[k++] = right[j++];
        }
        // One side ran out. What's left of the other is already sorted.
        while (i < left.length) merged[k++] = left[i++];
        while (j < right.length) merged[k++] = right[j++];
        return merged;
    }

    // Sorts nums in place. Not stable.
    static void quickSort(int[] nums) {
        quickSortRange(nums, 0, nums.length - 1);
    }

    static void quickSortRange(int[] nums, int lo, int hi) {
        if (lo >= hi) return; // 0 or 1 elements: already sorted.
        int p = partition(nums, lo, hi);
        // The pivot is in its final place. Sort each side of it.
        quickSortRange(nums, lo, p - 1);
        quickSortRange(nums, p + 1, hi);
    }

    // Lomuto partition of nums[lo..hi] around its middle element. Smaller values
    // end up left of the pivot, the rest right. Returns the pivot's final index.
    static int partition(int[] nums, int lo, int hi) {
        int mid = lo + (hi - lo) / 2;
        swap(nums, mid, hi); // Park the pivot at the end.
        int pivot = nums[hi];
        int store = lo; // nums[lo..store - 1] are all smaller than the pivot.
        for (int i = lo; i < hi; i++) {
            if (nums[i] < pivot) {
                swap(nums, i, store);
                store++;
            }
        }
        swap(nums, store, hi); // Put the pivot between the groups.
        return store;
    }

    static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public static void main(String[] args) {
        int[] a = {5, 2, 3, 1};
        int[] b = {5, 1, 1, 2, 0, 0};
        System.out.println(Arrays.toString(mergeSort(a))); // [1, 2, 3, 5]
        System.out.println(Arrays.toString(mergeSort(b))); // [0, 0, 1, 1, 2, 5]
        quickSort(a);
        quickSort(b);
        System.out.println(Arrays.toString(a)); // [1, 2, 3, 5]
        System.out.println(Arrays.toString(b)); // [0, 0, 1, 1, 2, 5]
    }
}

Worked Problems

Each solution stays folded until you open it, so you can try the problem first. Every one is a complete program in Python, TypeScript, Go, C# and Java, run and checked against its expected output.

Sort Colors

MEDIUMLeetCode 75

Problem

An array holds only the values 0, 1 and 2, standing for red, white and blue. Sort it in place so all the 0s come first, then the 1s, then the 2s. Don't use the library sort, and aim for a single pass with O(1) extra space.

Example: [2, 0, 2, 1, 1, 0] becomes [0, 0, 1, 1, 2, 2].

Show Solution

Approach

Counting works (count each value, then overwrite the array), but it takes two passes. The one-pass answer is Dijkstra's Dutch national flag partition. Three pointers split the array into four regions:

index    0  1  2  3  4  5  6  7  8
nums     0  0  1  1  ?  ?  ?  2  2
               ^     ^     ^
              low   mid   high

nums[0..low - 1]      all 0s
nums[low..mid - 1]    all 1s
nums[mid..high]       not checked yet
nums[high + 1..]      all 2s
  • nums[mid] is 0: swap it to low and advance both. The value that comes back from low is a 1 that was already checked (or, when low == mid, the same 0), so mid can move on.
  • nums[mid] is 1: it's already in the right region, so advance mid.
  • nums[mid] is 2: swap it to high and move high left. Don't advance mid, because the value that just arrived from high hasn't been checked.

Sort Colors, Step by Step

Step 1 of 8

nums

  • Being checked or swapped
  • In its region

Left of low go the 0s, from low to mid - 1 the 1s, and right of high the 2s. At the start, all of [2, 0, 2, 1, 1, 0] is unchecked.

All 8 steps as text
  1. Left of low go the 0s, from low to mid - 1 the 1s, and right of high the 2s. At the start, all of [2, 0, 2, 1, 1, 0] is unchecked.
  2. nums[0] = 2, so swap it to high and move high left. mid stays put, because the 0 that came back from index 5 hasn't been checked.
  3. nums[0] = 0 and low == mid, so it's already in the 0s. Advance both to 1.
  4. nums[1] = 0 and low == mid, so it's already in the 0s. Advance both to 2.
  5. nums[2] = 2, so swap it to high and move high left. mid stays put, because the 1 that came back from index 4 hasn't been checked.
  6. nums[2] = 1 is already in the 1s region, so just advance mid to 3.
  7. nums[3] = 1 is already in the 1s region, so just advance mid to 4.
  8. mid passed high, so nothing is left unchecked: [0, 0, 1, 1, 2, 2]. Every step advanced mid or pulled high back, so there were at most 6 of them.

Every step either advances mid or pulls high back, so the unchecked region shrinks by one each time and the loop runs at most n times. This three-way partition is the same fix that keeps quicksort fast when the array has many equal values.

Time O(n)Space O(1)

def sort_colors(nums: list[int]) -> None:
    """Sorts a list of 0s, 1s and 2s in place, in one pass (Dutch national flag)."""
    # nums[0..low - 1] are 0s, nums[low..mid - 1] are 1s and nums[high + 1..] are 2s.
    # nums[mid..high] hasn't been checked yet.
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            # The value that comes back from low was already checked, so mid moves on.
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            # The value that comes back from high is unchecked, so mid stays put.
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1


if __name__ == "__main__":
    a = [2, 0, 2, 1, 1, 0]
    b = [2, 0, 1]
    c = [1, 1, 0, 2, 0]
    sort_colors(a)
    sort_colors(b)
    sort_colors(c)
    print(a)  # [0, 0, 1, 1, 2, 2]
    print(b)  # [0, 1, 2]
    print(c)  # [0, 0, 1, 1, 2]
// Sorts an array of 0s, 1s and 2s in place, in one pass (Dutch national flag).
export function sortColors(nums: number[]): void {
  // nums[0..low - 1] are 0s, nums[low..mid - 1] are 1s and nums[high + 1..] are 2s.
  // nums[mid..high] hasn't been checked yet.
  let low = 0;
  let mid = 0;
  let high = nums.length - 1;
  while (mid <= high) {
    if (nums[mid] === 0) {
      // The value that comes back from low was already checked, so mid moves on.
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++;
      mid++;
    } else if (nums[mid] === 1) {
      mid++;
    } else {
      // The value that comes back from high is unchecked, so mid stays put.
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
    }
  }
}

const a = [2, 0, 2, 1, 1, 0];
const b = [2, 0, 1];
const c = [1, 1, 0, 2, 0];
sortColors(a);
sortColors(b);
sortColors(c);
console.log(JSON.stringify(a)); // [0,0,1,1,2,2]
console.log(JSON.stringify(b)); // [0,1,2]
console.log(JSON.stringify(c)); // [0,0,1,1,2]
package main

import "fmt"

// sortColors sorts a slice of 0s, 1s and 2s in place, in one pass (Dutch
// national flag).
func sortColors(nums []int) {
	// nums[0..low - 1] are 0s, nums[low..mid - 1] are 1s and nums[high + 1..] are 2s.
	// nums[mid..high] hasn't been checked yet.
	low, mid, high := 0, 0, len(nums)-1
	for mid <= high {
		switch nums[mid] {
		case 0:
			// The value that comes back from low was already checked, so mid moves on.
			nums[low], nums[mid] = nums[mid], nums[low]
			low++
			mid++
		case 1:
			mid++
		default:
			// The value that comes back from high is unchecked, so mid stays put.
			nums[mid], nums[high] = nums[high], nums[mid]
			high--
		}
	}
}

func main() {
	a := []int{2, 0, 2, 1, 1, 0}
	b := []int{2, 0, 1}
	c := []int{1, 1, 0, 2, 0}
	sortColors(a)
	sortColors(b)
	sortColors(c)
	fmt.Println(a) // [0 0 1 1 2 2]
	fmt.Println(b) // [0 1 2]
	fmt.Println(c) // [0 0 1 1 2]
}
using System;

public class Solution
{
    // Sorts an array of 0s, 1s and 2s in place, in one pass (Dutch national flag).
    public static void SortColors(int[] nums)
    {
        // nums[0..low - 1] are 0s, nums[low..mid - 1] are 1s and nums[high + 1..] are 2s.
        // nums[mid..high] hasn't been checked yet.
        int low = 0, mid = 0, high = nums.Length - 1;
        while (mid <= high)
        {
            if (nums[mid] == 0)
            {
                // The value that comes back from low was already checked, so mid moves on.
                (nums[low], nums[mid]) = (nums[mid], nums[low]);
                low++;
                mid++;
            }
            else if (nums[mid] == 1)
            {
                mid++;
            }
            else
            {
                // The value that comes back from high is unchecked, so mid stays put.
                (nums[mid], nums[high]) = (nums[high], nums[mid]);
                high--;
            }
        }
    }

    public static void Main()
    {
        int[] a = { 2, 0, 2, 1, 1, 0 };
        int[] b = { 2, 0, 1 };
        int[] c = { 1, 1, 0, 2, 0 };
        SortColors(a);
        SortColors(b);
        SortColors(c);
        Console.WriteLine(Format(a)); // [0, 0, 1, 1, 2, 2]
        Console.WriteLine(Format(b)); // [0, 1, 2]
        Console.WriteLine(Format(c)); // [0, 0, 1, 1, 2]
    }

    static string Format(int[] values) => "[" + string.Join(", ", values) + "]";
}
import java.util.Arrays;

public class Solution {
    // Sorts an array of 0s, 1s and 2s in place, in one pass (Dutch national flag).
    static void sortColors(int[] nums) {
        // nums[0..low - 1] are 0s, nums[low..mid - 1] are 1s and nums[high + 1..] are 2s.
        // nums[mid..high] hasn't been checked yet.
        int low = 0, mid = 0, high = nums.length - 1;
        while (mid <= high) {
            if (nums[mid] == 0) {
                // The value that comes back from low was already checked, so mid moves on.
                swap(nums, low, mid);
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else {
                // The value that comes back from high is unchecked, so mid stays put.
                swap(nums, mid, high);
                high--;
            }
        }
    }

    static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public static void main(String[] args) {
        int[] a = {2, 0, 2, 1, 1, 0};
        int[] b = {2, 0, 1};
        int[] c = {1, 1, 0, 2, 0};
        sortColors(a);
        sortColors(b);
        sortColors(c);
        System.out.println(Arrays.toString(a)); // [0, 0, 1, 1, 2, 2]
        System.out.println(Arrays.toString(b)); // [0, 1, 2]
        System.out.println(Arrays.toString(c)); // [0, 0, 1, 1, 2]
    }
}

Largest Number

MEDIUMLeetCode 179

Problem

Given a list of non-negative integers, arrange them so that, written side by side, they form the largest possible number. Return it as a string, since it can be far too big for any integer type.

Example: [3, 30, 34, 5, 9] returns "9534330".

Show Solution

Approach

Neither obvious order works. By value, 30 goes before 3 and you get 303. Reverse alphabetical order fails the same way: "30" comes after "3" alphabetically, so reversing puts it first and you get 303 again. The right answer is 330.

So compare two pieces by the only thing that matters: which order reads bigger when you glue them together. Put a before b when a + b > b + a as strings. "3" + "30" = "330" beats "303", so 3 goes first. The two glued strings have the same length, so comparing them as strings compares them as numbers, and nothing can overflow.

Is it safe to sort with that rule? A comparator has to be consistent, or the sort can return garbage. This one is. As numbers, a + b > b + a exactly when a / (10^len(a) - 1) > b / (10^len(b) - 1), so the rule quietly sorts by a fixed key per number. One edge case is left: for [0, 0] the pieces join to "00", so return "0" when the first piece is "0".

Time O(d · n log n), d = digits per numberSpace O(d · n)

from functools import cmp_to_key


def largest_number(nums: list[int]) -> str:
    """The largest number you can write by putting every value in `nums` side by side."""
    parts = [str(num) for num in nums]
    parts.sort(key=cmp_to_key(compare))
    # If the biggest piece is "0", every piece is, and "00" should read "0".
    if parts[0] == "0":
        return "0"
    return "".join(parts)


def compare(a: str, b: str) -> int:
    """Negative when a should come first, which is when "a then b" is the bigger number."""
    ab, ba = a + b, b + a
    # Both have the same length, so comparing them as strings compares the numbers.
    if ab > ba:
        return -1
    if ab < ba:
        return 1
    return 0


if __name__ == "__main__":
    print(largest_number([10, 2]))  # 210
    print(largest_number([3, 30, 34, 5, 9]))  # 9534330
    print(largest_number([0, 0]))  # 0
    print(largest_number([432, 43243]))  # 43243432
// The largest number you can write by putting every value in `nums` side by side.
export function largestNumber(nums: number[]): string {
  const parts = nums.map(String);
  parts.sort(compare);
  // If the biggest piece is "0", every piece is, and "00" should read "0".
  if (parts[0] === "0") return "0";
  return parts.join("");
}

// Negative when a should come first, which is when "a then b" is the bigger number.
function compare(a: string, b: string): number {
  const ab = a + b;
  const ba = b + a;
  // Both have the same length, so comparing them as strings compares the numbers.
  if (ab > ba) return -1;
  if (ab < ba) return 1;
  return 0;
}

console.log(largestNumber([10, 2])); // 210
console.log(largestNumber([3, 30, 34, 5, 9])); // 9534330
console.log(largestNumber([0, 0])); // 0
console.log(largestNumber([432, 43243])); // 43243432
package main

import (
	"fmt"
	"slices"
	"strconv"
	"strings"
)

// largestNumber returns the largest number you can write by putting every
// value in nums side by side.
func largestNumber(nums []int) string {
	parts := make([]string, len(nums))
	for i, num := range nums {
		parts[i] = strconv.Itoa(num)
	}
	slices.SortFunc(parts, compare)
	// If the biggest piece is "0", every piece is, and "00" should read "0".
	if parts[0] == "0" {
		return "0"
	}
	return strings.Join(parts, "")
}

// compare is negative when a should come first, which is when "a then b" is
// the bigger number.
func compare(a, b string) int {
	ab, ba := a+b, b+a
	// Both have the same length, so comparing them as strings compares the numbers.
	if ab > ba {
		return -1
	}
	if ab < ba {
		return 1
	}
	return 0
}

func main() {
	fmt.Println(largestNumber([]int{10, 2}))           // 210
	fmt.Println(largestNumber([]int{3, 30, 34, 5, 9})) // 9534330
	fmt.Println(largestNumber([]int{0, 0}))            // 0
	fmt.Println(largestNumber([]int{432, 43243}))      // 43243432
}
using System;
using System.Linq;

public class Solution
{
    // The largest number you can write by putting every value in nums side by side.
    public static string LargestNumber(int[] nums)
    {
        string[] parts = nums.Select(num => num.ToString()).ToArray();
        Array.Sort(parts, Compare);
        // If the biggest piece is "0", every piece is, and "00" should read "0".
        if (parts[0] == "0") return "0";
        return string.Concat(parts);
    }

    // Negative when a should come first, which is when "a then b" is the bigger number.
    static int Compare(string a, string b)
    {
        string ab = a + b, ba = b + a;
        // Both have the same length, so comparing them as strings compares the numbers.
        return string.CompareOrdinal(ba, ab);
    }

    public static void Main()
    {
        Console.WriteLine(LargestNumber(new[] { 10, 2 })); // 210
        Console.WriteLine(LargestNumber(new[] { 3, 30, 34, 5, 9 })); // 9534330
        Console.WriteLine(LargestNumber(new[] { 0, 0 })); // 0
        Console.WriteLine(LargestNumber(new[] { 432, 43243 })); // 43243432
    }
}
import java.util.Arrays;

public class Solution {
    // The largest number you can write by putting every value in nums side by side.
    static String largestNumber(int[] nums) {
        String[] parts = Arrays.stream(nums).mapToObj(String::valueOf).toArray(String[]::new);
        Arrays.sort(parts, Solution::compare);
        // If the biggest piece is "0", every piece is, and "00" should read "0".
        if (parts[0].equals("0")) return "0";
        return String.join("", parts);
    }

    // Negative when a should come first, which is when "a then b" is the bigger number.
    static int compare(String a, String b) {
        String ab = a + b, ba = b + a;
        // Both have the same length, so comparing them as strings compares the numbers.
        return ba.compareTo(ab);
    }

    public static void main(String[] args) {
        System.out.println(largestNumber(new int[] {10, 2})); // 210
        System.out.println(largestNumber(new int[] {3, 30, 34, 5, 9})); // 9534330
        System.out.println(largestNumber(new int[] {0, 0})); // 0
        System.out.println(largestNumber(new int[] {432, 43243})); // 43243432
    }
}

Common Pitfalls

  • Calling JavaScript's sort() on numbers without a comparator. It compares them as strings, so [10, 9, 1] becomes [1, 10, 9].
  • Assuming every library sort is stable. Go's slices.Sort and C#'s Array.Sort can reorder equal elements.
  • Always using the first or last element as quicksort's pivot, which turns already sorted input into O(n²).
  • Writing a broken comparator: returning a boolean instead of a negative, zero or positive number in JavaScript, or returning a - b in Java or C# when the subtraction can overflow. Use Integer.compare(a, b) or a.CompareTo(b).
  • Advancing mid after swapping a 2 to the back in Sort Colors. The value that came forward hasn't been checked yet.

Practice

More problems to try on your own.