Counting sort

countsort.rb

=begin
O(n + k)
=end

def countSort arr

  countArr = []
  resultArr = Array.new(arr.length)
  max = arr.max

  for i in 0..max
    countArr[i] = 0
  end

  arr.each_with_index do |value, index|
    countArr[value] += 1
  end

  j = 0
  while countArr.length - 1 != j
    countArr[j+1] = countArr[j] + countArr[j+1]
    j += 1
  end

  j = 0
  while arr.length  != j
    value = countArr[arr[j]]
    resultArr[value] = arr[j]
    countArr[arr[j]] -= 1
    j += 1
  end
  resultArr
end

newArr = [3,1,4,5,6,9,5]

puts countSort(newArr)

# Output => 
#         1
#         3
#         4
#         5
#         5
#         6
#         9