# Counting sort (Scala)

Other implementations: C | C# | Haskell | Java | Python, functional | Scala

Here is a simple Counting sort in Scala:

```<<counting_sort>>=
/**
*
* @param array : array to sort
* @param end   : number of elements to sort
* @param max   : upper bound for array values
* @param min   : lower bound for array values
*/
def cSort( array: Array[Int], end: Int, max: Int, min: Int): Unit = {
// precondition
assume( end <= array.length
&& array.subArray(0, end).forall( x => (min <= x && x <= max))) ;
if ( end < 2) {}  // nothing to sort
else if (end == 2) {
if (array( 0) > array(1)) {
// swap values
val temp = array(0) ;
array(0) = array(1) ;
array(1) = temp ;
}
}
else  {
val sortRange = max - min +1
val count = new Array[Int]( sortRange)
val scratch = new Array[Int]( end)
def normalized( i: Int) = array( i) - min
count_values_and_accumulate
// now count(normValue) == topmost (if repeated values) of order( normValue)
// reposition array values in scratch
// each value at count( normValue) position
// decrementing count( normValue) for next position of repeated values
for (val i <- Iterator.range( 0, end)) {
val normValue = normalized( i) ;
scratch( count( normValue) -1) = array(i) ;
count( normValue) = count( normValue) -1 ;
}
// copy scratch ordered values back into array
for (val i <- Iterator.range( 0, end)) {
array(i) = scratch( i)
}
}
}
```

Count normalized values and accumulate counters, so each accumulated counter will hold the topmost ordered position for the value it indexes.

```<<count_values_and_accumulate>>=
// init counters
for (val i <- Iterator.range( 0, sortRange)){
count( i) = 0 ;
}
// count normalized array values
for (val i <- Iterator.range( 0, end)) {
val normValue = normalized( i) ;
count( normValue) = count( normValue) +1 ;
}
// accumulate counters
for (val i <- Iterator.range( 1, sortRange)) {
count( i) = count( i) + count( i -1)
}
/**
* count(normValue) will hold the number of elements
* with normalized value less than or equal to normValue,
* so the topmost (for repeated values) order position
*
* {count(normValue) == 'count elements x where (normalized( x) <= normValue')}
*/
```

## Test module

```<<CountingSortTest.scala>>=
package test;
import scala.testing.UnitTest ;
object CountingSortTest extends Application {
counting_sort
def test = {
val sample1 = Array( 5, 3, 7, 10, 2, 7, 3)
val expected1 = Array( 2, 3, 3, 5, 7, 7, 10)
val min = List.fromArray( sample1) reduceLeft { (x: Int, y: Int) => Math.min( x,y)} ;
val max = List.fromArray( sample1) reduceLeft { (x: Int, y: Int) => Math.max( x,y)} ;
val actual1 = {
cSort( sample1, sample1.length, max, min) ;
sample1
}
UnitTest.assertSameElements(  actual1, expected1)
}
test
}
```

## Testing

```scala test.CountingSortTest
passed ok
```