Sort first: what sorting buys you

Python · closest/closest.py

"""The two van departures closest in time: every pair, or sort first and compare neighbours only."""

# Seconds after midnight of each departure, in the order the depots reported them: positions 0 to 7.
MORNING = [30125, 29830, 31400, 30050, 29955, 31310, 30990, 29700]
# Two vans that left in the same second (positions 0 and 2).
NOON = [43200, 43260, 43200]


def closest_brute(times):
    """Every pair of positions, n(n - 1)/2 gaps. Returns (gap, first position, second position)."""
    best = None
    for i in range(len(times)):
        for j in range(i + 1, len(times)):
            gap = abs(times[i] - times[j])
            if best is None or gap < best[0]:
                best = (gap, i, j)
    return best


def closest_sorted(times):
    """Sort the positions by time, then compare each departure with the next one only: n - 1 gaps."""
    order = sorted(range(len(times)), key=lambda i: times[i])
    best = None
    for a, b in zip(order, order[1:]):
        gap = times[b] - times[a]
        if best is None or gap < best[0]:
            best = (gap, min(a, b), max(a, b))
    return best


def show(name, times):
    print(f"{name}, {len(times)} departures")
    for plan, find in (("every pair", closest_brute), ("sorted first", closest_sorted)):
        gap, i, j = find(times)
        print(f"  {plan}: positions {i} and {j}, {gap} s apart")


if __name__ == "__main__":
    show("Morning", MORNING)
    show("Noon", NOON)

Morning, 8 departures
  every pair: positions 0 and 3, 75 s apart
  sorted first: positions 0 and 3, 75 s apart
Noon, 3 departures
  every pair: positions 0 and 2, 0 s apart
  sorted first: positions 0 and 2, 0 s apart

JavaScript · closest/closest.mjs

// The two van departures closest in time: every pair, or sort first and compare neighbours only.

// Seconds after midnight of each departure, in the order the depots reported them: positions 0 to 7.
const MORNING = [30125, 29830, 31400, 30050, 29955, 31310, 30990, 29700];
// Two vans that left in the same second (positions 0 and 2).
const NOON = [43200, 43260, 43200];

// Every pair of positions, n(n - 1)/2 gaps. Returns [gap, first position, second position].
function closestBrute(times) {
  let best = null;
  for (let i = 0; i < times.length; i++) {
    for (let j = i + 1; j < times.length; j++) {
      const gap = Math.abs(times[i] - times[j]);
      if (best === null || gap < best[0]) best = [gap, i, j];
    }
  }
  return best;
}

// Sort the positions by time, then compare each departure with the next one only: n - 1 gaps.
// Without the comparator, sort() would compare the numbers as strings.
function closestSorted(times) {
  const order = times.map((_, i) => i).sort((a, b) => times[a] - times[b]);
  let best = null;
  for (let k = 0; k + 1 < order.length; k++) {
    const [a, b] = [order[k], order[k + 1]];
    const gap = times[b] - times[a];
    if (best === null || gap < best[0]) best = [gap, Math.min(a, b), Math.max(a, b)];
  }
  return best;
}

function show(name, times) {
  console.log(`${name}, ${times.length} departures`);
  for (const [plan, find] of [["every pair", closestBrute], ["sorted first", closestSorted]]) {
    const [gap, i, j] = find(times);
    console.log(`  ${plan}: positions ${i} and ${j}, ${gap} s apart`);
  }
}

show("Morning", MORNING);
show("Noon", NOON);

Morning, 8 departures
  every pair: positions 0 and 3, 75 s apart
  sorted first: positions 0 and 3, 75 s apart
Noon, 3 departures
  every pair: positions 0 and 2, 0 s apart
  sorted first: positions 0 and 2, 0 s apart

Java · compiled/Closest.java

import java.util.Arrays;
import java.util.Comparator;

// The two van departures closest in time: every pair, or sort first and compare neighbours only.
public class Closest {
    record Answer(int gap, int first, int second) {}

    // Every pair of positions, n(n - 1)/2 gaps.
    static Answer closestBrute(int[] times) {
        Answer best = null;
        for (int i = 0; i < times.length; i++) {
            for (int j = i + 1; j < times.length; j++) {
                int gap = Math.abs(times[i] - times[j]);
                if (best == null || gap < best.gap()) best = new Answer(gap, i, j);
            }
        }
        return best;
    }

    // Sort the positions by time, then compare each departure with the next one only: n - 1 gaps.
    // An int[] cannot be sorted with a comparator, so the positions are boxed as Integer.
    static Answer closestSorted(int[] times) {
        Integer[] order = new Integer[times.length];
        for (int i = 0; i < order.length; i++) order[i] = i;
        Arrays.sort(order, Comparator.comparingInt(i -> times[i]));
        Answer best = null;
        for (int k = 0; k + 1 < order.length; k++) {
            int a = order[k], b = order[k + 1];
            int gap = times[b] - times[a];
            if (best == null || gap < best.gap()) best = new Answer(gap, Math.min(a, b), Math.max(a, b));
        }
        return best;
    }

    static void show(String name, int[] times) {
        System.out.println(name + ", " + times.length + " departures");
        Answer[] answers = {closestBrute(times), closestSorted(times)};
        String[] plans = {"every pair", "sorted first"};
        for (int p = 0; p < 2; p++) {
            Answer x = answers[p];
            System.out.println("  " + plans[p] + ": positions " + x.first() + " and " + x.second() + ", " + x.gap() + " s apart");
        }
    }

    public static void main(String[] args) {
        // Seconds after midnight of each departure, in the order the depots reported them: positions 0 to 7.
        show("Morning", new int[] {30125, 29830, 31400, 30050, 29955, 31310, 30990, 29700});
        // Two vans that left in the same second (positions 0 and 2).
        show("Noon", new int[] {43200, 43260, 43200});
    }
}

C++ · compiled/closest.cpp

// The two van departures closest in time: every pair, or sort first and compare neighbours only.
#include <algorithm>
#include <cstdlib>
#include <numeric>
#include <print>
#include <string_view>
#include <vector>

struct Answer {
    int gap = -1;  // -1: nothing compared yet
    int first = 0;
    int second = 0;
};

// Every pair of positions, n(n - 1)/2 gaps.
Answer closest_brute(const std::vector<int>& times) {
    Answer best;
    for (int i = 0; i < std::ssize(times); ++i) {
        for (int j = i + 1; j < std::ssize(times); ++j) {
            int gap = std::abs(times[i] - times[j]);
            if (best.gap < 0 || gap < best.gap) best = {gap, i, j};
        }
    }
    return best;
}

// Sort the positions by time, then compare each departure with the next one only: n - 1 gaps.
Answer closest_sorted(const std::vector<int>& times) {
    std::vector<int> order(times.size());
    std::iota(order.begin(), order.end(), 0);  // 0, 1, 2, ...
    std::sort(order.begin(), order.end(), [&](int a, int b) { return times[a] < times[b]; });
    Answer best;
    for (std::size_t k = 0; k + 1 < order.size(); ++k) {
        int a = order[k], b = order[k + 1];
        int gap = times[b] - times[a];
        if (best.gap < 0 || gap < best.gap) best = {gap, std::min(a, b), std::max(a, b)};
    }
    return best;
}

void show(std::string_view name, const std::vector<int>& times) {
    std::println("{}, {} departures", name, times.size());
    for (auto [plan, answer] : {std::pair{"every pair", closest_brute(times)}, std::pair{"sorted first", closest_sorted(times)}}) {
        std::println("  {}: positions {} and {}, {} s apart", plan, answer.first, answer.second, answer.gap);
    }
}

int main() {
    // Seconds after midnight of each departure, in the order the depots reported them: positions 0 to 7.
    show("Morning", {30125, 29830, 31400, 30050, 29955, 31310, 30990, 29700});
    // Two vans that left in the same second (positions 0 and 2).
    show("Noon", {43200, 43260, 43200});
}

Go · compiled/closest.go

// The two van departures closest in time: every pair, or sort first and compare neighbours only.
package main

import (
	"cmp"
	"fmt"
	"slices"
)

type answer struct{ gap, first, second int }

// closestBrute compares every pair of positions: n(n - 1)/2 gaps.
func closestBrute(times []int) answer {
	best := answer{gap: -1}
	for i := range times {
		for j := i + 1; j < len(times); j++ {
			gap := max(times[i]-times[j], times[j]-times[i])
			if best.gap < 0 || gap < best.gap {
				best = answer{gap, i, j}
			}
		}
	}
	return best
}

// closestSorted sorts the positions by time, then compares each departure with the next one only: n - 1 gaps.
func closestSorted(times []int) answer {
	order := make([]int, len(times))
	for i := range order {
		order[i] = i
	}
	slices.SortFunc(order, func(a, b int) int { return cmp.Compare(times[a], times[b]) })
	best := answer{gap: -1}
	for k := 0; k+1 < len(order); k++ {
		a, b := order[k], order[k+1]
		if gap := times[b] - times[a]; best.gap < 0 || gap < best.gap {
			best = answer{gap, min(a, b), max(a, b)}
		}
	}
	return best
}

func show(name string, times []int) {
	fmt.Printf("%s, %d departures\n", name, len(times))
	for _, plan := range []struct {
		name   string
		answer answer
	}{{"every pair", closestBrute(times)}, {"sorted first", closestSorted(times)}} {
		fmt.Printf("  %s: positions %d and %d, %d s apart\n", plan.name, plan.answer.first, plan.answer.second, plan.answer.gap)
	}
}

func main() {
	// Seconds after midnight of each departure, in the order the depots reported them: positions 0 to 7.
	show("Morning", []int{30125, 29830, 31400, 30050, 29955, 31310, 30990, 29700})
	// Two vans that left in the same second (positions 0 and 2).
	show("Noon", []int{43200, 43260, 43200})
}

Build and run all three · compiled/closest_session.py

from session import run, versions

# Closest.java runs as a single source file, closest.cpp is built with the sanitizers on, and go run builds closest.go.
versions("java -version", "clang++ --version", "go version")
run("""
java Closest.java
clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined closest.cpp -o closest && ./closest
go run closest.go
""")

# openjdk version "25.0.4.1" LTS
# Apple clang version 21.0.0 (clang-2100.3.34.2)
# go version go1.27.1 darwin/arm64
$ java Closest.java
Morning, 8 departures
  every pair: positions 0 and 3, 75 s apart
  sorted first: positions 0 and 3, 75 s apart
Noon, 3 departures
  every pair: positions 0 and 2, 0 s apart
  sorted first: positions 0 and 2, 0 s apart
$ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined closest.cpp -o closest && ./closest
Morning, 8 departures
  every pair: positions 0 and 3, 75 s apart
  sorted first: positions 0 and 3, 75 s apart
Noon, 3 departures
  every pair: positions 0 and 2, 0 s apart
  sorted first: positions 0 and 2, 0 s apart
$ go run closest.go
Morning, 8 departures
  every pair: positions 0 and 3, 75 s apart
  sorted first: positions 0 and 3, 75 s apart
Noon, 3 departures
  every pair: positions 0 and 2, 0 s apart
  sorted first: positions 0 and 2, 0 s apart

Python · stability/stability.py

"""A class register in alphabetical order, sorted by grade: does each grade keep the register's order?"""

# (name, grade) in alphabetical order of name, the order of the class register.
REGISTER = [
    ("Aarav", "B"), ("Bea", "A"), ("Chen", "A"), ("Divya", "B"), ("Elif", "B"), ("Farah", "A"),
    ("Gopal", "A"), ("Hana", "C"), ("Ishaan", "C"), ("Jonas", "C"), ("Kavya", "B"), ("Leo", "C"),
    ("Meera", "C"), ("Noor", "B"), ("Omar", "C"), ("Priya", "C"), ("Quinn", "A"), ("Ravi", "B"),
    ("Sana", "B"), ("Tomas", "A"), ("Uma", "B"), ("Vikram", "C"), ("Wen", "A"), ("Zoya", "A"),
]
# What a stable sort by grade must give: grade A in register order, then grade B, then grade C.
STABLE = [s for grade in "ABC" for s in REGISTER if s[1] == grade]


def report(sort_name, students):
    moved = sum(1 for got, want in zip(students, STABLE) if got != want)
    grade_a = " ".join(name for name, grade in students if grade == "A")
    print(f"{sort_name} ({moved} of {len(students)} moved)")
    print(f"  grade A: {grade_a}")


report("sorted()", sorted(REGISTER, key=lambda s: s[1]))

in_place = list(REGISTER)
in_place.sort(key=lambda s: s[1])
report("list.sort()", in_place)

sorted() (0 of 24 moved)
  grade A: Bea Chen Farah Gopal Quinn Tomas Wen Zoya
list.sort() (0 of 24 moved)
  grade A: Bea Chen Farah Gopal Quinn Tomas Wen Zoya

JavaScript · stability/stability.mjs

// A class register in alphabetical order, sorted by grade: does each grade keep the register's order?

// [name, grade] in alphabetical order of name, the order of the class register.
const REGISTER = [
  ["Aarav", "B"], ["Bea", "A"], ["Chen", "A"], ["Divya", "B"], ["Elif", "B"], ["Farah", "A"],
  ["Gopal", "A"], ["Hana", "C"], ["Ishaan", "C"], ["Jonas", "C"], ["Kavya", "B"], ["Leo", "C"],
  ["Meera", "C"], ["Noor", "B"], ["Omar", "C"], ["Priya", "C"], ["Quinn", "A"], ["Ravi", "B"],
  ["Sana", "B"], ["Tomas", "A"], ["Uma", "B"], ["Vikram", "C"], ["Wen", "A"], ["Zoya", "A"],
];
// What a stable sort by grade must give: grade A in register order, then grade B, then grade C.
const STABLE = ["A", "B", "C"].flatMap((grade) => REGISTER.filter((s) => s[1] === grade));

function report(sortName, students) {
  const moved = students.filter((s, i) => s !== STABLE[i]).length;
  const gradeA = students.filter((s) => s[1] === "A").map((s) => s[0]).join(" ");
  console.log(`${sortName} (${moved} of ${students.length} moved)`);
  console.log(`  grade A: ${gradeA}`);
}

const byGrade = (x, y) => (x[1] === y[1] ? 0 : x[1] < y[1] ? -1 : 1);

report("Array.prototype.sort", [...REGISTER].sort(byGrade));
report("Array.prototype.toSorted", REGISTER.toSorted(byGrade));

Array.prototype.sort (0 of 24 moved)
  grade A: Bea Chen Farah Gopal Quinn Tomas Wen Zoya
Array.prototype.toSorted (0 of 24 moved)
  grade A: Bea Chen Farah Gopal Quinn Tomas Wen Zoya

Java · compiled/Stability.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.StringJoiner;

// A class register in alphabetical order, sorted by grade: does each grade keep the register's order?
public class Stability {
    record Student(String name, char grade) {}

    // In alphabetical order of name, the order of the class register.
    static final List<Student> REGISTER = List.of(
        new Student("Aarav", 'B'), new Student("Bea", 'A'), new Student("Chen", 'A'), new Student("Divya", 'B'),
        new Student("Elif", 'B'), new Student("Farah", 'A'), new Student("Gopal", 'A'), new Student("Hana", 'C'),
        new Student("Ishaan", 'C'), new Student("Jonas", 'C'), new Student("Kavya", 'B'), new Student("Leo", 'C'),
        new Student("Meera", 'C'), new Student("Noor", 'B'), new Student("Omar", 'C'), new Student("Priya", 'C'),
        new Student("Quinn", 'A'), new Student("Ravi", 'B'), new Student("Sana", 'B'), new Student("Tomas", 'A'),
        new Student("Uma", 'B'), new Student("Vikram", 'C'), new Student("Wen", 'A'), new Student("Zoya", 'A'));

    static void report(String sortName, List<Student> students) {
        List<Student> stable = new ArrayList<>();  // what a stable sort by grade must give
        for (char grade : "ABC".toCharArray()) {
            for (Student s : REGISTER) if (s.grade() == grade) stable.add(s);
        }
        int moved = 0;
        StringJoiner gradeA = new StringJoiner(" ");
        for (int i = 0; i < students.size(); i++) {
            if (!students.get(i).equals(stable.get(i))) moved++;
            if (students.get(i).grade() == 'A') gradeA.add(students.get(i).name());
        }
        System.out.println(sortName + " (" + moved + " of " + students.size() + " moved)");
        System.out.println("  grade A: " + gradeA);
    }

    public static void main(String[] args) {
        Comparator<Student> byGrade = Comparator.comparingInt(Student::grade);

        List<Student> list = new ArrayList<>(REGISTER);
        list.sort(byGrade);
        report("List.sort", list);

        Student[] array = REGISTER.toArray(new Student[0]);
        Arrays.sort(array, byGrade);
        report("Arrays.sort on objects", Arrays.asList(array));
    }
}

C++ · compiled/stability.cpp

// A class register in alphabetical order, sorted by grade: does each grade keep the register's order?
#include <algorithm>
#include <print>
#include <string>
#include <string_view>
#include <vector>

struct Student {
    std::string name;
    char grade;
    bool operator==(const Student&) const = default;
};

// In alphabetical order of name, the order of the class register.
const std::vector<Student> kRegister = {
    {"Aarav", 'B'}, {"Bea", 'A'},  {"Chen", 'A'},  {"Divya", 'B'},  {"Elif", 'B'},   {"Farah", 'A'},
    {"Gopal", 'A'}, {"Hana", 'C'}, {"Ishaan", 'C'}, {"Jonas", 'C'}, {"Kavya", 'B'},  {"Leo", 'C'},
    {"Meera", 'C'}, {"Noor", 'B'}, {"Omar", 'C'},  {"Priya", 'C'},  {"Quinn", 'A'},  {"Ravi", 'B'},
    {"Sana", 'B'},  {"Tomas", 'A'}, {"Uma", 'B'},  {"Vikram", 'C'}, {"Wen", 'A'},    {"Zoya", 'A'},
};

void report(std::string_view sort_name, const std::vector<Student>& students) {
    std::vector<Student> stable;  // what a stable sort by grade must give
    for (char grade : {'A', 'B', 'C'}) {
        for (const Student& s : kRegister) {
            if (s.grade == grade) stable.push_back(s);
        }
    }
    int moved = 0;
    std::string grade_a;
    for (std::size_t i = 0; i < students.size(); ++i) {
        if (students[i] != stable[i]) ++moved;
        if (students[i].grade == 'A') grade_a += (grade_a.empty() ? "" : " ") + students[i].name;
    }
    std::println("{} ({} of {} moved)", sort_name, moved, students.size());
    std::println("  grade A: {}", grade_a);
}

int main() {
    auto by_grade = [](const Student& x, const Student& y) { return x.grade < y.grade; };

    auto a = kRegister;
    std::sort(a.begin(), a.end(), by_grade);
    report("std::sort", a);

    auto b = kRegister;
    std::stable_sort(b.begin(), b.end(), by_grade);
    report("std::stable_sort", b);
}

Go · compiled/stability.go

// A class register in alphabetical order, sorted by grade: does each grade keep the register's order?
package main

import (
	"cmp"
	"fmt"
	"slices"
	"sort"
	"strings"
)

type student struct {
	name  string
	grade byte
}

// In alphabetical order of name, the order of the class register.
var register = []student{
	{"Aarav", 'B'}, {"Bea", 'A'}, {"Chen", 'A'}, {"Divya", 'B'}, {"Elif", 'B'}, {"Farah", 'A'},
	{"Gopal", 'A'}, {"Hana", 'C'}, {"Ishaan", 'C'}, {"Jonas", 'C'}, {"Kavya", 'B'}, {"Leo", 'C'},
	{"Meera", 'C'}, {"Noor", 'B'}, {"Omar", 'C'}, {"Priya", 'C'}, {"Quinn", 'A'}, {"Ravi", 'B'},
	{"Sana", 'B'}, {"Tomas", 'A'}, {"Uma", 'B'}, {"Vikram", 'C'}, {"Wen", 'A'}, {"Zoya", 'A'},
}

func report(sortName string, students []student) {
	var stable []student // what a stable sort by grade must give
	for _, grade := range []byte("ABC") {
		for _, s := range register {
			if s.grade == grade {
				stable = append(stable, s)
			}
		}
	}
	moved := 0
	var gradeA []string
	for i, s := range students {
		if s != stable[i] {
			moved++
		}
		if s.grade == 'A' {
			gradeA = append(gradeA, s.name)
		}
	}
	fmt.Printf("%s (%d of %d moved)\n", sortName, moved, len(students))
	fmt.Printf("  grade A: %s\n", strings.Join(gradeA, " "))
}

func main() {
	a := slices.Clone(register)
	sort.Slice(a, func(i, j int) bool { return a[i].grade < a[j].grade })
	report("sort.Slice", a)

	b := slices.Clone(register)
	sort.SliceStable(b, func(i, j int) bool { return b[i].grade < b[j].grade })
	report("sort.SliceStable", b)

	byGrade := func(x, y student) int { return cmp.Compare(x.grade, y.grade) }

	c := slices.Clone(register)
	slices.SortFunc(c, byGrade)
	report("slices.SortFunc", c)

	d := slices.Clone(register)
	slices.SortStableFunc(d, byGrade)
	report("slices.SortStableFunc", d)
}

Build and run all three · compiled/stability_session.py

from session import run, versions

# The same register sorted by grade with each language's sorts: Java, then C++, then Go.
versions("java -version", "clang++ --version", "go version")
run("""
java Stability.java
clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined stability.cpp -o stability && ./stability
go run stability.go
""")

# openjdk version "25.0.4.1" LTS
# Apple clang version 21.0.0 (clang-2100.3.34.2)
# go version go1.27.1 darwin/arm64
$ java Stability.java
List.sort (0 of 24 moved)
  grade A: Bea Chen Farah Gopal Quinn Tomas Wen Zoya
Arrays.sort on objects (0 of 24 moved)
  grade A: Bea Chen Farah Gopal Quinn Tomas Wen Zoya
$ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined stability.cpp -o stability && ./stability
std::sort (23 of 24 moved)
  grade A: Zoya Bea Chen Wen Tomas Farah Gopal Quinn
std::stable_sort (0 of 24 moved)
  grade A: Bea Chen Farah Gopal Quinn Tomas Wen Zoya
$ go run stability.go
sort.Slice (23 of 24 moved)
  grade A: Quinn Bea Chen Zoya Wen Farah Gopal Tomas
sort.SliceStable (0 of 24 moved)
  grade A: Bea Chen Farah Gopal Quinn Tomas Wen Zoya
slices.SortFunc (23 of 24 moved)
  grade A: Quinn Bea Chen Zoya Wen Farah Gopal Tomas
slices.SortStableFunc (0 of 24 moved)
  grade A: Bea Chen Farah Gopal Quinn Tomas Wen Zoya