Java Sorting Algorithms — Overview, Complexity, and Stability
Fast recall
Quick revision
Core answer
Arrays.sort and Collections.sort use TimSort (for objects) or Dual-Pivot Quicksort (for primitives) under the hood. Comparison-based sorts: Bubble sort — O(n²) average and worst, O(1) space, stable, used only for teaching. Insertion sort — O(n²) worst, O(n) on nearly-sorted, O(1) space, stable, used for small subarrays inside hybrid sorts. Merge sort — O(n log n) all cases, O(n) space, stable, predictable, used for linked lists and external sorting. Quicksort — O(n log n) average, O(n²) worst (bad pivots), O(log n) stack space, not stable, fastest in practice for arrays due to cache locality. Heapsort — O(n log n) all cases, O(1) space, not stable, used when O(1) space is required and stability isn't needed. Non-comparison sorts: Counting sort — O(n + k) where k = range, stable, only for bounded integers. Radix sort — O(d · (n + b)) where d = digits, b = base; stable. Bucket sort — O(n + k) average; works when input is uniformly distributed. Stability matters when sorting by multiple keys (e.g., sort by name then by age — a stable sort preserves the first-key order within equal second-key groups). Java's choice: TimSort for objects (stable, adaptive, O(n log n) worst, O(n) for nearly-sorted) — best of all worlds for general use. Dual-Pivot Quicksort for primitives (no stability needed for int[], faster cache behavior). For interviews: know complexity, stability, and when each is preferred. Don't reinvent — use Arrays.sort / Collections.sort in production.Whether the candidate knows time/space complexity of major sorting algorithms, the concept of stability, and Java's actual sort implementations (TimSort, Dual-Pivot Quicksort)
Confusing average and worst case (quicksort O(n log n) avg vs O(n²) worst). Saying merge sort is O(1) space (it's O(n)). Forgetting non-comparison sorts. Not knowing TimSort is what Java uses
Mention TimSort and Dual-Pivot Quicksort by name, discuss stability and when it matters, address O(n log n) lower bound for comparison sorts and how non-comparison breaks it, mention external sorting
Interview-ready guide
Interview answer
Sorting algorithms — two classes
Comparison-based
- Lower bound: Ω(n log n)
- Bubble, insertion, selection: O(n²)
- Merge, quicksort, heapsort: O(n log n) average
Non-comparison
- Counting, radix, bucket: O(n) when applicable
- Don't compare pairwise; use value structure directly
- Beat the lower bound when range is bounded
Major sorts
Bubble sort
- O(n²) average and worst
- O(1) space, stable
- Teaching only; never in production
Selection sort
- O(n²) all cases
- O(1) space, not stable
- Notable: minimum swaps (n-1)
Insertion sort
- O(n) best (nearly-sorted), O(n²) worst
- O(1) space, stable
- Used in hybrid sorts for small subarrays
Merge sort
- O(n log n) guaranteed all cases
- O(n) space (auxiliary array)
- Stable
- Best for linked lists, external sort
Quicksort
- O(n log n) average, O(n²) worst (bad pivot)
- O(log n) stack space
- Not stable
- Fastest in practice for arrays (cache locality)
- Mitigations: random pivot, median-of-three, dual-pivot
Heapsort
- O(n log n) all cases
- O(1) space
- Not stable
- Slower than quicksort due to cache-unfriendly heap
TimSort
- Hybrid: merge sort + insertion sort
- Detects existing runs (sorted subsequences)
- O(n) on sorted, O(n log n) worst
- Stable
- Java's default for object arrays since Java 7
Non-comparison sorts
Counting sort
- O(n + k), k = range
- Stable
- Bounded integer keys (ages, grades)
Radix sort
- O(d · (n + b)), d = digits
- Stable
- Integers, fixed-length strings
Bucket sort
- O(n + k) average
- Uniformly distributed data
Stability
- Equal elements retain original relative order
- Matters for multi-key sorts
- Sort by name then stably by age → sorted by age then name within age
Stable
- Bubble, insertion, merge, TimSort, counting, radix
Unstable
- Selection, quicksort, heapsort
Java's choice
TimSort for object arrays
- Stable
- Adaptive (O(n) on sorted)
- O(n log n) worst
- Best of all worlds
Dual-Pivot Quicksort for primitive arrays
- Two pivots instead of one
- ~10-20% faster than single-pivot
- Stability irrelevant for primitives (can't tell two int 5's apart)
Java APIs
`Arrays.sort(int[])` — Dual-Pivot Quicksort
`Arrays.sort(Object[])` — TimSort
`Collections.sort(List)` — TimSort
`Arrays.parallelSort(...)` — parallel merge sort
`Stream.sorted(...)` — TimSort, returns new
`TreeMap` / `TreeSet` — maintains order on insert (red-black tree)
Choosing the right sort
Default: Arrays.sort / Collections.sort — TimSort
Primitive max speed: Arrays.sort(int[]) — Dual-Pivot
Parallel, large: Arrays.parallelSort(...)
O(1) space critical: heapsort
Linked lists: merge sort
Bounded ints: counting sort
Mostly sorted: TimSort wins (O(n) best case)
Top-K, not full sort: heap (O(n log k)) or QuickSelect (O(n) avg)
Just min/max: O(n) scan, not sort
Common mistakes
1. Confusing average and worst
- Quicksort O(n log n) avg, O(n²) worst
- Merge sort O(n log n) ALL cases
2. Saying merge sort is O(1) space
- It's O(n) auxiliary
3. Forgetting non-comparison sorts
- Counting / radix can be O(n)
4. Not knowing Java uses TimSort
- For objects, since Java 7
5. Reinventing sort
- Use built-ins; they're well-tested
Don't use in production
- Bubble, selection — always worse than insertion
Recommendation: Always use Java's built-in sorts in production: Arrays.sort for objects (TimSort — stable, adaptive, O(n log n) worst, O(n) best case for nearly-sorted), Arrays.sort(int[]) for primitives (Dual-Pivot Quicksort — fastest), Arrays.parallelSort for large arrays (parallel merge sort, threshold ~8K), Collections.sort (delegates to TimSort), or Stream.sorted (TimSort, returns new). For interviews, know the complexity table cold — best/average/worst time, space, and stability for each algorithm. Understand the Ω(n log n) lower bound for comparison sorts and how non-comparison sorts (counting, radix, bucket) break it for bounded-range integers. Know why TimSort is Java's choice: stable + adaptive + worst-case O(n log n) is hard to beat. Know why Dual-Pivot Quicksort wins for primitives: stability is meaningless, and the cache-friendly two-pivot partitioning is ~10-20% faster. Understand stability: it matters for multi-key sorts; use stable algorithms or augment with original index. For specialized scenarios: merge sort for linked lists and external sort; heapsort when O(1) space matters; counting sort for bounded integers; radix sort for fixed-length strings or integers; bucket sort for uniformly distributed data. Don't use bubble or selection sort in production — always worse than insertion. For top-K, use a heap or QuickSelect — don't full-sort. The mental model: comparison sorts are bounded by O(n log n); structure-aware sorts can do O(n); Java's TimSort and Dual-Pivot Quicksort handle 99% of cases.
Java Sorting Algorithms — Overview, Complexity, and Stability
Direct Answer
Sorting algorithms fall into two broad classes: comparison-based (O(n log n) lower bound) and non-comparison (O(n) for bounded-range integers). Java's Arrays.sort and Collections.sort use TimSort (for objects) or Dual-Pivot Quicksort (for primitives) under the hood. Comparison-based sorts: Bubble sort — O(n²) average and worst, O(1) space, stable, used only for teaching. Insertion sort — O(n²) worst, O(n) on nearly-sorted, O(1) space, stable, used for small subarrays inside hybrid sorts. Merge sort — O(n log n) all cases, O(n) space, stable, predictable, used for linked lists and external sorting. Quicksort — O(n log n) average, O(n²) worst (bad pivots), O(log n) stack space, not stable, fastest in practice for arrays due to cache locality. Heapsort — O(n log n) all cases, O(1) space, not stable, used when O(1) space is required and stability isn't needed. Non-comparison sorts: Counting sort — O(n + k) where k = range, stable, only for bounded integers. Radix sort — O(d · (n + b)) where d = digits, b = base; stable. Bucket sort — O(n + k) average; works when input is uniformly distributed. Stability matters when sorting by multiple keys (e.g., sort by name then by age — a stable sort preserves the first-key order within equal second-key groups). Java's choice: TimSort for objects (stable, adaptive, O(n log n) worst, O(n) for nearly-sorted) — best of all worlds for general use. Dual-Pivot Quicksort for primitives (no stability needed for int[], faster cache behavior). For interviews: know complexity, stability, and when each is preferred. Don't reinvent — use Arrays.sort / Collections.sort in production.
Common Mistakes & Pitfalls
Confusing average and worst case (quicksort O(n log n) avg vs O(n²) worst). Saying merge sort is O(1) space (it's O(n)). Forgetting non-comparison sorts. Not knowing TimSort is what Java uses
Check your understanding
Answer these without looking back at the article.
- Why does Java use TimSort for object arrays and Dual-Pivot Quicksort for primitives?
- What does it mean for a sort to be stable, and why does it matter?
- How do non-comparison sorts beat the O(n log n) lower bound?
- Why is quicksort faster than heapsort in practice despite both being O(n log n)?
- When would you choose merge sort over quicksort?
Related interview prep categories
1Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.