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?

Bloxberg

You mean a new semigroup instance whose binary operation uses radix sort to preserve ordering? – Agonistic

Yes. – Morey

You can't "write an algorithm (sort or otherwise) as a monoid". You may be able to formulate the algorithm using monoids, as in the answer to your other question #21878072 – Fearful

Thanks @AlexeyRomanov - that's helpful - I've updated the question. – Bloxberg

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

Tenon

Thanks @Meir - assuming I want a radix sort - how would you go about it? – Bloxberg

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.

Festival

Suppose I want to write my own data structures? – Bloxberg

@hawkeye, I don't understand the significance of who writes the data structures. Could you explain? – Festival