package object radixSort {
  /**
   * Least-significant-digit-first radix sort for integer arrays.
   * Sorts the argument array in ascending order.
   * Assumes that all the integers are non-negative.
   * Interpret 'digit' as 'byte' (8 bits) here and use bit-level operations
   *  such as shifting (>> and <<) and masking (&) to extract 'digits'.
   */
  def byteToInt(n: Int, shiftRight: Int): Int = {
    (n >> shiftRight) & 0xFF
  }

  def cumulate(a: Array[Int]): Array[Int] = {
    var index = 0
    var cumulative = 0
    while (index < a.length) {
      val t = a(index)
      a(index) = cumulative
      cumulative += t
      index += 1
    }
    a
  }

  def lsdRadixSort(a: Array[Int]): Unit = {
    val N = a.length
    if(N <= 1) return

    var byteSize = 8
    var intSize = 32
    var shiftBy = 0

    while(shiftBy < intSize) {
      var count = Array.fill(256)(0)
      var result = Array.fill(N)(0)

      var i = 0
      while (i < N) {
        count(byteToInt(a(i), shiftBy)) += 1
        i += 1
      }
      if (count(0) == N) return
      count = cumulate(count)
      i = 0
      while(i < N) {
        val target = byteToInt(a(i), shiftBy)
        result(count(target)) = a(i)
        count(target) = count(target) + 1
        i += 1
      }
      i = 0
      while(i < N) {
        a(i) = result(i)
        i += 1
      }

      shiftBy += byteSize
    }
  }
}