Performance Characteristics of Sorting
What you'll learn: You'll understand why sorting takes O(n log n) time on average and why ArrayList is faster to sort than LinkedList.
Why O(n log n)?
When you call Collections.sort(), Java uses a sophisticated algorithm called Timsort (a hybrid of merge sort and insertion sort). The key insight is that sorting requires comparing elements many times. For n elements, you can't just look at each element once—you need roughly n × log₂(n) comparisons to put everything in order.
Think of sorting a deck of 8 cards. You can't sort it with just 8 comparisons; you need about 8 × 3 = 24 comparison operations. This O(n log n) grows much slower than O(n²) but faster than O(n).
ArrayList vs LinkedList: The Hidden Cost
Here's where implementation matters dramatically:
ArrayList wins decisively because:
- Random access is O(1): The sorting algorithm can instantly jump to any element by index
- Memory locality: Elements sit consecutively in memory, making the CPU cache very happy
- No pointer chasing: Direct array access is fast
LinkedList struggles because:
- Random access is O(n): To reach element [i], you must traverse i nodes from the head
- Poor cache performance: Nodes are scattered across memory
- Extra object overhead: Each node carries pointer references
Even though LinkedList has O(1) insertion at known positions, sorting requires accessing elements repeatedly by position—exactly what LinkedList is worst at. The sorting algorithm's O(n log n) comparisons multiply with LinkedList's O(n) access cost, creating terrible real-world performance.
Key Takeaway: Collections.sort runs in O(n log n) time, but always sort an ArrayList—never a LinkedList. If you must sort a LinkedList, copy it to an ArrayList first, sort, then copy back if needed.