Sorting Algorithms

Sort with the library

In real code you almost never write a sort. Java’s is well-tested and faster than anything you would write under time pressure.

int[] values = {5, 2, 9, 1};
Arrays.sort(values);                  // {1, 2, 5, 9}

List<String> names = new ArrayList<>(List.of("carol", "alice", "bob"));
Collections.sort(names);              // alphabetical
names.sort(null);                     // same thing

The algorithms below are worth understanding anyway — they explain why sorting costs what it does, and the ideas behind them reappear elsewhere.

Selection sort

Repeatedly find the smallest remaining element and swap it into place.

static void selectionSort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        int smallest = i;
        for (int j = i + 1; j < a.length; j++) {
            if (a[j] < a[smallest]) {
                smallest = j;
            }
        }
        int temp = a[i];
        a[i] = a[smallest];
        a[smallest] = temp;
    }
}

Simple and easy to verify, but it always scans the whole remaining array, so it costs the same whether the input is already sorted or completely shuffled.

Insertion sort

Take each element and slide it backwards into its correct position among the already-sorted portion.

static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int value = a[i];
        int j = i - 1;

        while (j >= 0 && a[j] > value) {
            a[j + 1] = a[j];          // shift right
            j--;
        }
        a[j + 1] = value;
    }
}

The j >= 0 test must come first — swap the two conditions and you read a[-1].

Insertion sort has a genuinely useful property: on nearly-sorted data the inner loop barely runs, making it close to linear. This is why real library sorts switch to insertion sort for small or nearly-ordered chunks.

Merge sort

Split the array in half, sort each half, then merge the two sorted halves.

static void mergeSort(int[] a, int low, int high) {
    if (low >= high) return;                    // 0 or 1 element is sorted

    int mid = low + (high - low) / 2;
    mergeSort(a, low, mid);
    mergeSort(a, mid + 1, high);
    merge(a, low, mid, high);
}

static void merge(int[] a, int low, int mid, int high) {
    int[] merged = new int[high - low + 1];
    int i = low, j = mid + 1, k = 0;

    while (i <= mid && j <= high) {
        merged[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    }
    while (i <= mid)  merged[k++] = a[i++];     // leftovers from the left
    while (j <= high) merged[k++] = a[j++];     // leftovers from the right

    System.arraycopy(merged, 0, a, low, merged.length);
}

The two trailing while loops matter — one side always runs out first, and its remainder must still be copied.

Merge sort guarantees its performance regardless of input, but needs a temporary array. Using <= in the comparison keeps it stable, meaning equal elements retain their original relative order.

Quicksort

Choose a pivot, move everything smaller to its left and everything larger to its right, then sort each side.

static void quickSort(int[] a, int low, int high) {
    if (low >= high) return;

    int pivot = a[high];
    int boundary = low;

    for (int i = low; i < high; i++) {
        if (a[i] < pivot) {
            int t = a[i]; a[i] = a[boundary]; a[boundary] = t;
            boundary++;
        }
    }
    int t = a[boundary]; a[boundary] = a[high]; a[high] = t;   // pivot into place

    quickSort(a, low, boundary - 1);
    quickSort(a, boundary + 1, high);
}

Usually the fastest in practice and needs no extra array. Its weakness is pivot choice: consistently picking the smallest or largest element degrades it badly. On already-sorted input this version does exactly that, which is why real implementations choose the pivot more carefully.

Costs

Comparing the sorts

The last two rows explain a real Java quirk: Arrays.sort uses a different algorithm for primitives than for objects. Primitives get a quicksort variant (fast, not stable). Objects get a merge sort variant (stable, guaranteed). So sorting int[] and Integer[] behave differently, which occasionally matters.

Sorting your own objects

Supply a comparator describing the order:

class Motor {
    String name;
    int port;
    Motor(String name, int port) { this.name = name; this.port = port; }
}

List<Motor> motors = new ArrayList<>();
// ...

motors.sort(Comparator.comparingInt(m -> m.port));                    // by port
motors.sort(Comparator.comparingInt((Motor m) -> m.port).reversed()); // descending
motors.sort(Comparator.comparing((Motor m) -> m.name)
                      .thenComparingInt(m -> m.port));                // tie-break

The explicit (Motor m) is required once you chain .reversed() or .thenComparing — Java can no longer infer the lambda’s parameter type without it, and the error message when you omit it is unhelpful.

motors.sort((a, b) -> a.port - b.port);              // risky
motors.sort((a, b) -> Integer.compare(a.port, b.port));  // correct

Stability

A stable sort keeps equal elements in their original relative order. That lets you sort by several keys in stages:

motors.sort(Comparator.comparing(m -> m.name));    // first by name
motors.sort(Comparator.comparingInt(m -> m.port)); // then by port
// within equal ports, still ordered by name

This only works because List.sort is stable. Chaining with thenComparing is usually clearer, but the staged approach is handy when the sort keys are decided at different points in the program.

Next

Related