Counting Sort

Counting Sort is a non-comparison-based sorting algorithm that sorts integers by counting the occurrences of each distinct value in a range and using this information to place elements in their correct positions. It works in 𝑂(𝑛+𝑘) time, where 𝑛 is the number of elements and 𝑘 is the range of the input values. Counting Sort is efficient for small ranges of integers but unsuitable for sorting non-integer or large-range data due to its space complexity of 𝑂(𝑘). It is a stable sorting algorithm when implemented correctly.

Source Code Listing

code.ts

/**
 * @file Counting Sort
 * @author Dustin Boston
 * @see Cormen, T, Leiserson, C, Rivest, R, and Stein, C. (2001).
 *   Introduction to Algorithms. (2nd ed). The MIT Press.
 */

/**
 * Sorts an array of non-negative integers using the counting sort algorithm.
 * This algorithm is efficient for sorting numbers within a small range.
 *
 * @param unsortedArray The array of non-negative integers to be sorted.
 * @param maxValueInArray The maximum value in the array. Used to find the range
 *   of vals.
 * @returns A new array containing the sorted elements.
 */
export function countingSort(
  unsortedArray: number[],
  sortedArray: number[],
  maxValueInArray: number,
): void {
  const counts: number[] = Array.from({length: maxValueInArray + 1}, () => 0);

  // Update the `count` array with positions of elements in the sorted array
  for (const element of unsortedArray) {
    counts[element]++;
  }

  for (let i = 1; i <= maxValueInArray; i++) {
    counts[i] += counts[i - 1];
  }

  for (let index = unsortedArray.length - 1; index >= 0; index--) {
    sortedArray[counts[unsortedArray[index]] - 1] = unsortedArray[index];
    counts[unsortedArray[index]]--;
  }
}

test.ts

import {describe, expect, test} from "bun:test";
import {countingSort} from "./code.ts";

describe("Counting Sort", () => {
  test("Sort", () => {
    const unsortedArray = [2, 5, 3, 0, 2, 3, 0, 3];
    const maxValueInArray = Math.max(...unsortedArray);
    const sortedArray: number[] = Array.from(
      {length: unsortedArray.length},
      () => 0,
    );

    countingSort(unsortedArray, sortedArray, maxValueInArray);

    const expectedArray = [0, 0, 2, 2, 3, 3, 3, 5].toString();
    const actualArray = sortedArray.toString();
    expect(actualArray).toBe(expectedArray);
  });
});