O(n log n) describes a linearithmic growth rate: sorting a collection requires work proportional to its size multiplied by its logarithm. In Clojure, sort and sort-by use this performance profile, making collection size important when processing large datasets. section 8.3.5
For sorting operations, the practical implications are:
- Expect O(n log n) steps and O(n) memory for sort and sort-by. section 8.3.5
- Review sorting on large datasets; around 100,000 entries, the linearithmic cost may become noticeable. section 8.3.5
- Timsort detects ordered segments, extends short segments with insertion sort, and merges them. section 8.3.5
Sorting a collection
(sort > [18 43 3 0 9]) ;; (43 18 9 3 0) The result is descending, while the sorting work follows the O(n log n) profile. section 8.3.5
