🛠️ merge insertion sort in clojure

Merge Insertion Sort is a Clojure(script) library that implements the Merge Insertion sorting algorithm (also known as the Ford-Johnson Algorithm).

Merge Insertion Sort is a comparison sort that minimizes the worst-case number of comparisons for small N (and has been proven optimal for N < 18, and likely optimal for N < 47).

I like to think of it as "the most efficient sorting algorithm that nobody uses." As I warn in the README:

This algorithm will not make your programs faster. Even though it has a better worst-case for small N than most other algorithms, its implementation results in worse performance on actual computers than simpler algorithms (like quicksort, timsort and merge sort).

When developing Decidedly So, I realized the app would benefit from minimizing the number of pairwise comparisons a user needed to do, but I couldn't find an existing implementation in Clojure, so I wrote it.

The code is not very "idiomatic" - lots of atoms instead of, say, pure functions - but it works™.

For you Comp Sci geeks out there, the repo's README goes into much more detail about the algorithm, and features this step-by-step explanatory graphic: