##
# Given a non-negative integer value_upper_bound and an array of integers arr with values between 0 and value_upper_bound,
# returns a sorted copy of the input array.
# When value_upper_bound = O(arr.length), sorting runs in O(arr.length).

def counting_sort(arr, value_upper_bound)
    if !value_upper_bound.integer? || value_upper_bound < 0
        raise ArgumentError.new("counting_sort must be invoked with integer value_upper_bound >= 0")
    end
    if !arr.all? { |elem| elem.integer? && elem.between?(0, value_upper_bound) }
        raise ArgumentError.new("counting_sort must be invoked with integer array elements in (0..value_upper_bound)")
    end
    sorted_arr = Array.new(arr.length) { 0 }
    tmp_arr = Array.new(value_upper_bound+1) { 0 }
    for elem in arr
        tmp_arr[elem] += 1
    end
    for i in 1..value_upper_bound
        tmp_arr[i] += tmp_arr[i-1]
    end
    arr.reverse_each do |elem|
        sorted_arr[tmp_arr[elem]-1] = elem
        tmp_arr[elem] -= 1
    end
    sorted_arr
end

Problem Statement

Given an unsorted array of n elements, write a function to sort the array.

Approach

• Find out the maximum element (let's call it max) from the given array.
• Initialize an array of length max+1 with all elements set to 0 to store the array's count.
• Store the count of each element at their respective index in the array's count.
• Store cumulative sum of the elements of the count array. It helps in placing the elements into the correct index of the sorted array.
• Find the index of each element of the original array in the array's count. This gives the cumulative count.
• Place the element at the index calculated and decrease its count by one.

Time Complexity

O(n+k): where k is the range of the non-negative key values.

Space Complexity

O(n+k): where k is the range of the non-negative key values.

Founder's Name

• Harold H. Seward.

Example

countingSort(array, size)
  max <- find largest element in array
  initialize count array with all zeros
  for j <- 0 to size
    find the total count of each unique element and
    store the count at jth index in count array
  for i <- 1 to max
    find the cumulative sum and store it in count array itself
  for j <- size down to 1
    restore the elements to array
    decrease count of each element restored by 1

Video Explanation

A video explaining the Counting Sort Algorithm

Animation Explanation

Counting Sort visualization