How can I optimize the timing of this CountingSort algorithm in Scala

Question

I would like to ask you for help to identify which part of my code is not efficient. I am comparing the QuickSort algorithm with the CountingSort algorithm, assuming that the number of elements in an Array[Byte] is less than 16.

However, the CountingSort time is much higher than the QuickSort time, in all the tests I had performed sequentially. Then, I wanted to test this code in Spark to compute the Median Filter, but the results of the distributed execution times are consistent with the sequential execution times. What I mean is that QuickSort is always faster than CountingSort, even for smaller arrays.

Evidently something in my code is hanging the final processing.

This is the code:

def Histogram(Input: Array[Byte]) : Array[Int] = {
  val result = Array.ofDim[Int](256)
  val range = Input.distinct.map(x => x & 0xFF)
  val mx = Input.map(x => x & 0xFF).max
  for (h <- range)
    result(h) = Input.count(x => (x & 0xFF) == h)
  result.slice(0, mx + 1)
}

def CummulativeSum(Input: Array[Int]): Array[Long] = Input.map(x => x.toLong).scanLeft(0.toLong)(_ + _).drop(1)

def CountingSort(Input: Array[Byte]): Array[Byte] = {
  val hist = Histogram(Input)
  val cum = CummulativeSum(hist)
  val Output = Array.fill[Byte](Input.length)(0)
  for (i <- Input.indices) {
    Output(cum(Input(i) & 0xFF).toInt - 1) = Input(i)
    cum(Input(i) & 0xFF) -= 1
  }
  Output
}

Answer 1

You can build your histogram without traversing the input quite so many times.

def histogram(input :Array[Byte]) :Array[Int] = {
  val inputMap :Map[Int,Array[Byte]] = input.groupBy(_ & 0xFF)
                                            .withDefaultValue(Array())
  Array.tabulate(inputMap.keys.max+1)(inputMap(_).length)
}

I'm not sure if this is much faster, but it is certainly more concise.

def countingSort(input :Array[Byte]) :Array[Byte] =
  histogram(input).zipWithIndex.flatMap{case (v,x) => Seq.fill(v)(x.toByte)}

My tests show it produces the same results but there could be edge conditions that I've missed.