Radix sort in Nim.

radix.nim

## Radix sort in O(n) unlike other sorting methods that can be way worse.
## But radix sort needs the bits to operate on, which makes it different then
## other sorting algorithms.

proc getMax(arr: seq[SomeInteger]): SomeInteger =
  for i, e in arr:
    if i == 0:
      result = e
    elif e > result:
      result = e


func intPow(a, b: uint64): uint64 =
  if b > 0:
    result = a
    for i in 1 ..< b:
      result *= a


template radixSortWithTmp[T](arr: ptr seq[T], tmp: var seq[T]) =
  # Meat of the radix sort algorithm.
  const
    base = 256
  var
    m = getMax(arr[])
    count = newSeq[T](base)
    exp: uint64 = 1

  while m div exp > 0:
    if exp != 1:
      for i in 0 ..< count.len:
        count[i] = 0

    for e in arr[]:
      inc count[(e div exp) mod base]

    for i in 1 ..< base:
      count[i] += count[i - 1]

    var i = arr[].len - 1
    while i >= 0:
      tmp[count[(arr[i] div exp) mod base] - 1] = arr[i]
      dec count[(arr[i] div exp) mod base]
      dec i

    for i in 0 ..< arr[].len:
      arr[i] = tmp[i]

    if uint64(exp) == intPow(base, (sizeof(T) - 1)):
      break

    exp *= base


proc radixSortBasic[T](arr: ptr seq[T]) =
  ## Setup radix sort for basic uints.
  var tmp = newSeq[T](arr[].len)
  radixSortWithTmp(arr, tmp)


proc radixSortNeg[T](arr: ptr seq[T]) =
  ## Negative integers are in two complement from,
  ## so we need to fix it post sort.
  var tmp = newSeq[T](arr[].len)
  radixSortWithTmp(arr, tmp)
  let neg = 1.uint64 shl (sizeof(T)*8 - 1)
  for i, e in arr[]:
    if e >= neg:
      for j in 0 ..< arr[].len:
        let numNeg = arr[].len - i
        if j < numNeg:
          arr[][j] = tmp[i + j]
        else:
          arr[][j] = tmp[j - i + 1]
      break

proc radixSortFloat[T](arr: ptr seq[T]) =
  ## Negative floats just have negative bit set,
  ## so we need to fix it post sort.
  var tmp = newSeq[T](arr[].len)
  radixSortWithTmp(arr, tmp)
  let neg = 1.uint64 shl (sizeof(T)*8 - 1)
  for i, e in arr[]:
    if e >= neg:
      for j in 0 ..< arr[].len:
        let numNeg = arr[].len - i
        if j < numNeg:
          arr[][j] = tmp[i + (numNeg - j - 1)]
        else:
          arr[][j] = tmp[j - i + 1]
      break


proc radixSort(arr: var seq[uint8]) = radixSortBasic[uint8](addr arr)
proc radixSort(arr: var seq[int8]) = radixSortNeg[uint8](cast[ptr seq[uint8]](addr arr))
proc radixSort(arr: var seq[uint16]) = radixSortBasic[uint16](addr arr)
proc radixSort(arr: var seq[int16]) = radixSortNeg[uint16](cast[ptr seq[uint16]](addr arr))
proc radixSort(arr: var seq[uint32]) = radixSortBasic[uint32](addr arr)
proc radixSort(arr: var seq[int32]) = radixSortNeg[uint32](cast[ptr seq[uint32]](addr arr))
proc radixSort(arr: var seq[uint64]) = radixSortBasic[uint64](addr arr)
proc radixSort(arr: var seq[int64|int]) = radixSortNeg[uint64](cast[ptr seq[uint64]](addr arr))
proc radixSort(arr: var seq[float64|float]) = radixSortFloat[uint64](cast[ptr seq[uint64]](addr arr))
proc radixSort(arr: var seq[float32]) = radixSortFloat[uint32](cast[ptr seq[uint32]](addr arr))


when isMainModule:
  import algorithm, times, random

  template timeIt(name: string, iter: int, fn: untyped) =
    let now = epochTime()
    for i in 0 ..< iter:
      fn
    echo name, " took ", (epochTime() - now)/float(iter), "s"


  timeIt "small radix", 1_000:
    var arr = @[170.uint64, 45, 75, 90, 802, 24, 2, 66, 0]
    radixSort(arr)

  timeIt "small algorithm.sort", 1_000:
    var arr = @[170.uint64, 45, 75, 90, 802, 24, 2, 66, 0]
    sort(arr)


  block:
    randomize(1877)
    var arr = newSeq[int]()
    for i in 0 .. 10_000:
      arr.add(rand(1000))

    timeIt "big radix", 100:
      radixSort(arr)

  block:
    randomize(1877)
    var arr = newSeq[int]()
    for i in 0 .. 10_000:
      arr.add(rand(1000))

    timeIt "big algorithm.sort", 100:
      sort(arr)

  block:
    var arr = @[170.uint64, 45, 75, 90, 802, 24, 2, 66, 0]
    radixSort(arr)
    echo arr

  block:
    var arr = @[170.uint32, 45, 75, 90, 802, 24, 2, 66, 0]
    radixSort(arr)
    echo arr

  block:
    var arr = @[170.uint16, 45, 75, 90, 802, 24, 2, 66, 0]
    radixSort(arr)
    echo arr

  block:
    var arr = @[170.uint8, 45, 75, 90, 255, 24, 2, 66, 0]
    radixSort(arr)
    echo arr

  block:
    var arr = @[170.int64, -45, 75, -90, 802, -24, 2, -66, 0]
    radixSort(arr)
    echo arr

  block:
    var arr = @[170.int32, -45, 75, -90, 802, -24, 2, -66, 0]
    radixSort(arr)
    echo arr

  block:
    var arr = @[170.int16, -45, 75, -90, 802, -24, 2, -66, 0]
    radixSort(arr)
    echo arr

  block:
    var arr = @[127.int8, -45, 75, -90, 127, -24, 2, -66, 0]
    radixSort(arr)
    echo arr

  block:
    var arr = @[170.float64, -45.1, 75.2, -90.3, 802.4, -24.5, 2.6, -66.7, 0.0]
    radixSort(arr)
    echo arr

  block:
    var arr = @[170.float32, -45.1, 75.2, -90.3, 802.4, -24.5, 2.6, -66.7, 0.0]
    radixSort(arr)
    echo arr