TimSort is a stable hybrid sorting algorithm used by Clojure's sort and sort-by. It exploits already ordered runs, extends short runs with insertion sort, then merges the ordered segments. section 8.3.5
Its practical characteristics are:
- Worst-case time is O(n log n), with O(n) memory allocation. section 8.3.5
- Performance should be reviewed for large collections; around 100,000 entries, sorting can become noticeably slower. section 8.3.5
- Clojure sorting accepts comparators, including predicates such as >, and sort-by derives ordering through a key function. section 8.3.5
Clojure examples
(sort [:a :z :h :e :w]) ;; (:a :e :h :w :z) (sort > [18 43 3 0 9]) ;; (43 18 9 3 0) (sort-by :age [{:age 65} {:age 13} {:age 8}]) ;; ({:age 8} {:age 13} {:age 65})
