Sorting Comparison

Prev Next

You've now coded five sorting algorithms by hand: Bubble, Selection, Insertion, Merge, and Quick sort. Interviewers rarely ask you to write a sixth from scratch — what they actually want is for you to pick the right one and justify the pick with time complexity, space complexity, stability, and whether it sorts in-place. This lesson puts all five side by side in one table, then looks at what Java's own Arrays.sort() does under the hood — which is not one algorithm, but two, chosen deliberately based on what you're sorting.

The Full Comparison Table

Algorithm	Best	Average	Worst	Space	Stable?	In-place?	When to use
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Yes	Yes	Teaching only — never in production code.
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	No	Yes	When the cost of swapping is very high and comparisons are cheap — it does the fewest swaps of any O(n²) sort (at most n−1).
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Yes	Yes	Small arrays (roughly n < 47, which is why TimSort and Dual-Pivot Quicksort fall back to it), or nearly-sorted/streaming data.
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes	No	When you need guaranteed O(n log n) with no worst-case cliff, or stability matters (e.g. sorting objects by a secondary key), or sorting linked lists/external data on disk.
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	No	Yes	General-purpose default for arrays — fastest in practice due to cache-friendly in-place partitioning, as long as pivot selection avoids the worst case.
`Arrays.sort()` (primitives)	O(n)	O(n log n)	O(n²)	O(log n)	N/A	Yes	Default choice for `int[]`, `double[]`, etc. — Dual-Pivot Quicksort.
`Arrays.sort()` (objects)	O(n)	O(n log n)	O(n log n)	O(n)	Yes	No	Default choice for `Integer[]`, `String[]`, any `Object[]` — TimSort.

Note: Quick Sort's average case beats Merge Sort in practice (better cache locality, fewer allocations) even though both are O(n log n) — but Quick Sort's O(n²) worst case (already-sorted input with a naive pivot, or an adversarial input) is a real risk Merge Sort never has. That's the whole trade-off in one sentence.

Why Java Splits Arrays.sort() Into Two Algorithms

This is a question worth understanding deeply, because it tests whether you understand why stability matters, not just what it means.

Stability means: if two elements are considered equal by the comparator, their relative order from the input is preserved in the output. This only matters when there is something to preserve beyond the compared value itself — i.e. when sorting objects that carry other fields, or when you're chaining multiple sorts (sort by last name, then stably sort by first name, and the last-name order survives for ties).

A primitive int has no identity beyond its value. Two 5s in an int[] are completely indistinguishable — there is no "other field" riding along with either one, so there is nothing for a stable sort to preserve. Since stability is unobservable for primitives, Java's engineers picked Dual-Pivot Quicksort for primitive arrays: it's unstable, but faster in practice (in-place, excellent cache behavior, no auxiliary array) and the downside of instability literally cannot be observed.

An Object[] (or any generic T[]) is different — each element is a distinct object with its own identity and possibly other fields, so instability would be a real, visible bug (e.g. re-sorting a list of Employee objects by department could silently scramble an earlier sort by name). So Java uses TimSort for objects: a stable, adaptive merge-sort/insertion-sort hybrid (it detects already-ordered "runs" in the data and merges them, falling back to insertion sort for small runs) — same O(n log n) guarantee as merge sort, with O(n) auxiliary space.

Seeing Both In Code

import java.util.Arrays;

public class SortDemo {
    public static void main(String[] args) {
        // primitive int[] -> Dual-Pivot Quicksort, unstable, in-place
        int[] nums = {5, 2, 9, 1, 5, 6};
        Arrays.sort(nums);
        System.out.println(Arrays.toString(nums)); // [1, 2, 5, 5, 6, 9]

        // Object[] (Integer[]) -> TimSort, stable, uses O(n) extra space
        Integer[] boxedNums = {5, 2, 9, 1, 5, 6};
        Arrays.sort(boxedNums);
        System.out.println(Arrays.toString(boxedNums)); // [1, 2, 5, 5, 6, 9]

        // Custom Comparator on objects still goes through TimSort
        String[] words = {"banana", "apple", "cherry"};
        Arrays.sort(words, (a, b) -> b.compareTo(a)); // descending
        System.out.println(Arrays.toString(words)); // [cherry, banana, apple]
    }
}

Time complexity: O(n log n) average for both calls (worst case O(n²) for the primitive Dual-Pivot Quicksort path, worst case O(n log n) for the TimSort object path). Space complexity: O(log n) for the primitive sort (recursion stack), O(n) for the object sort (TimSort's merge buffer).

A Decision Checklist For Interviews

Question to ask yourself	Points toward
Is n small (roughly < 50)?	Insertion sort — low overhead beats asymptotically better algorithms at small n.
Do I need a worst-case guarantee (real-time system, adversarial input)?	Merge sort — no O(n²) cliff.
Am I sorting objects and must preserve tie order?	Merge sort / TimSort — stability required.
Is memory tightly constrained (embedded, huge array)?	Quick sort or heap sort — O(log n) or O(1) extra space.
Is this just "sort this array" with no special constraint?	`Arrays.sort()` — don't hand-roll what the JDK already tuned.

Up next: Every sort you've written so far is a loop. Recursion Basics introduces the tool that makes Merge Sort, Quick Sort, tree traversals, and backtracking all possible — a function that calls itself.

Prev Next