Can you formulate a monoid or semigroup for the radix sort?

Question

This is the pseudocode for the radix sort:

Pseudocode for Radix Sort:
Radix-Sort(A, d)
// Each key in A[1..n] is a d-digit integer. (Digits are
// numbered 1 to d from right to left.)
1. for i = 1 to d do
Use a stable sorting algorithm to sort A on digit i.

This is the Scala code for the radix sort:

object RadixSort {
  val WARP_SIZE = 32

  def main(args: Array[String]) = {
    var A = Array(123,432,654,3123,654,2123,543,131,653,123)

    radixSortUintHost(A, 4).foreach(i => println(i))
  }

  // LSB radix sort
  def radixSortUintHost(A: Array[Int], bits: Int): Array[Int] = {
    var a = A
    var b = new Array[Int](a.length)

    var rshift = 0
    var mask = ~(-1 << bits)

    while (mask != 0) {
      val cntArray = new Array[Int](1 << bits)

      for (p <- 0 until a.length) {
        var key = (a(p) & mask) >> rshift
        cntArray(key)+= 1
      }

      for (i <- 1 until cntArray.length)
        cntArray(i) += cntArray(i-1)

      for (p <- a.length-1 to 0 by -1) {
        var key = (a(p) & mask) >> rshift
        cntArray(key)-= 1
        b(cntArray(key)) = a(p)
      }

      val temp = b
      b = a
      a = temp

      mask <<= bits
      rshift += bits
    }

    b
  }
}

This is the Haskell code for the radix sort:

import Data.Bits (Bits(testBit, bitSize))
import Data.List (partition)

lsdSort :: (Ord a, Bits a) => [a] -> [a]
lsdSort = fixSort positiveLsdSort

msdSort :: (Ord a, Bits a) => [a] -> [a]
msdSort = fixSort positiveMsdSort

-- Fix a sort that puts negative numbers at the end, like positiveLsdSort and positiveMsdSort
fixSort sorter list = uncurry (flip (++)) (break (< 0) (sorter list))

positiveLsdSort :: (Bits a) => [a] -> [a]
positiveLsdSort list = foldl step list [0..bitSize (head list)] where
step list bit = uncurry (++) (partition (not . flip testBit bit) list)

positiveMsdSort :: (Bits a) => [a] -> [a]
positiveMsdSort list = aux (bitSize (head list) - 1) list where
aux _ [] = []
aux (-1) list = list
aux bit list = aux (bit - 1) lower ++ aux (bit - 1) upper where
    (lower, upper) = partition (not . flip testBit bit) list

My question is: Can you formulate a monoid or semigroup for the radix sort?

Answer 1

The radix sort invariant is that the data is sorted using the first k bits. If you want an operation that adds more data sorted or not, you are asking for merge sort functionality not radix. If what you are adding is bits of data to all records you could use a monoid.

Edit: The hart of a monoid is an associative operation. We can look at the sorting bits as a way of applying partial order. You injest the data for all records bit by bit. Each bit applies a partial order. This is associative you can merge some bits to get a more elaborate partial order. Note order is important but it is still associative.and thus can be.viewed as a monad

Answer 2

I think you may be thinking too literally about the idea of radix sort. Abstractly, I imagine the monoid you want is

1. Sorted lists with
2. Merging

The big question is how you want to represent the sorted lists. If you represent them as sorted Haskell lists, then the merge operation is the usual piece-by-piece merge used in merge sort. If you represent them in a more "radixy" fashion, then you'll have some variety of trie. You can probably find some algorithms around for merging tries. There's one in bytestring-trie, but nothing about its implementation seems to be documented.