Unveiling Java’s Hidden Sorting Engines: How Arrays.sort and Collections.sort Really Work

1. Arrays.sort() algorithm

Arrays.sort() has many overloads; for primitive int arrays it eventually uses a Dual‑Pivot Quicksort implementation. If the array length is below QUICKSORT_THRESHOLD (286), the dual‑pivot quicksort is applied. For lengths below INSERTION_SORT_THRESHOLD (47), insertion sort is used instead.

When the length is 286 or more, the algorithm first checks whether the array is already nearly sorted in ascending or descending order. If the order is good, it switches to a merge sort; otherwise it continues with the dual‑pivot quicksort.

Thus, large arrays that are partially ordered use merge sort, while others use dual‑pivot quicksort, and very small arrays use insertion sort.

2. Collections.sort() algorithm

Collections.sort() delegates to the sorting methods in Arrays. If the flag LegacyMergeSort.userRequested is true, a classic merge sort is used; otherwise the modern TimSort algorithm is applied.

The legacy merge sort is marked for possible removal in future Java versions.

3. Takeaway

When answering interview questions about Java sorting, mentioning the dual‑pivot quicksort, insertion sort thresholds, and TimSort demonstrates deeper understanding beyond simply stating “quick sort”.