Optimise `Data.Algebra.Array.sort`

[i-am-tom]

Currently, the sort function in Data.Algebra.Array is roughly equivalent to an insertion sort. This leads to a lot of duplicated comparisons. Ideally, this could be avoided by implementing something like an in-place heap sort. Open to suggestions, though :)

[nfgrusk]

Hey, it’s me again. This is somewhat of a follow-up to my tweets about the current implementation.

I think the sort function in Data.Algebra.Array is an implementation of selection sort. And, if you want to minimize the number of swaps, this is as good as it gets. It is neither stable nor stack-safe, though.

I may have found a solution that is stable, stack-safe, and an implementation of insertion sort. Here’s the catch: It returns an array of move operations. 😄

sortBy comparison
    = _.instructions
  <<< foldlWithIndex go { sortedArray: [], instructions: [] }
  where
    go offset acc@{ sortedArray, instructions } element
      = fromMaybe' (\_ → acc { sortedArray = snoc sortedArray element }) do
          -- The following is basically equivalent to
          --   { sortedArray: Array.insertBy comparison element acc.sortedArray
          --   , instructions: … }
          -- Because the array is sorted, `findIndex` can be replaced by a binary search.
          index   ← findIndex (\x → comparison element x == LT) sortedArray
          updated ← insertAt index element sortedArray
          pure { sortedArray:  updated
               , instructions: snoc instructions (Move offset index)
               }

What do you think about it? 😅