Java Arrays.sort Internals | Fresher Interview

The thing most people get wrong is assuming Arrays dot sort uses a single algorithm. It actually uses two, depending on what you're sorting. For primitive arrays, like int arrays or double arrays, it uses a dual-pivot quicksort. For object arrays, and also for Collections dot sort and List dot sort, it uses TimSort, which is a hybrid of merge sort and insertion sort. The reason for that split is stability. A stable sort keeps equal elements in their original relative order, and that matters a lot when you sort objects by a key, for example sorting employees by department while keeping the original ordering within each department. TimSort is stable, so it's the right choice for objects. Quicksort is not stable, but for primitives that's completely fine, because two equal integers are genuinely identical, there's no hidden information to preserve, so order among equal primitives is meaningless. That lets Java use the faster, in-place quicksort for primitives without any downside. The other nice property of TimSort is that it detects already-sorted runs in the data and merges them, so on real-world data that's partially ordered it runs close to linear time, while still guaranteeing O of n log n in the worst case. So my one-line summary is: dual-pivot quicksort for primitives because stability isn't needed, and stable, run-aware TimSort for objects because it usually is.