Stable vs Unstable Sorting
You'll learn what sort stability means and which Java sorting algorithms guarantee it.
What Is Sort Stability?
A stable sort preserves the relative order of elements that compare as equal according to the comparison criteria. An unstable sort may rearrange equal elements unpredictably.
Imagine sorting students by grade, where several have the same score. A stable sort keeps students with identical grades in their original order (perhaps alphabetically by name if that's how they started). An unstable sort might shuffle them randomly.
Stability in Java's Sorting Algorithms
Java provides different sorting guarantees depending on what you're sorting:
Collections.sort()andList.sort(): Stable — uses TimSort, which guarantees stability.Arrays.sort()for objects: Stable — also uses TimSort (since Java 7).Arrays.sort()for primitives: Unstable — uses Dual-Pivot Quicksort for performance.Arrays.parallelSort(): Unstable — parallel sorting trades stability for speed.
Why Stability Matters
Stability becomes critical when sorting by multiple criteria. If you first sort employees by department, then by salary (using a stable sort), employees with equal salaries remain ordered by department. An unstable sort would lose that departmental grouping.
When sorting by a single criterion or when all elements are distinct, stability doesn't affect the outcome—but it's still valuable for predictable, reproducible results in testing and debugging.
Choosing the Right Algorithm
Use stable sorts (Collections.sort(), List.sort(), Arrays.sort() for objects) when element order matters beyond the comparison key. Use Arrays.parallelSort() or primitive array sorting when performance is critical and stability is unnecessary.
Key Takeaway: Stable sorts preserve the original order of equal elements; Java's Collections.sort() and object Arrays.sort() are stable, while primitive sorting and parallel sorting are not.