# Counting Sort

## Introduction

Counting sort is an efficient sorting algorithm that can be used to sort elements in a range of integers. It is a non-comparison based sorting algorithm that works by counting the number of occurrences of each element in the array and then using this information to determine the position of each element in the sorted output array.

## Implementation

Here is an implementation of counting sort in OCaml:

```
let counting_sort arr =
let max_val = Array.fold_left (fun acc x -> max acc x) arr.(0) arr in
let count_arr = Array.make (max_val + 1) 0 in
Array.iter (fun x -> count_arr.(x) <- count_arr.(x) + 1) arr;
let index_arr = Array.make (max_val + 1) 0 in
let rec fill_index_arr i j =
if i <= max_val then
begin
index_arr.(i) <- j;
fill_index_arr (i + 1) (j + count_arr.(i))
end
in
fill_index_arr 0 0;
let sorted_arr = Array.make (Array.length arr) 0 in
Array.iteri (fun i x -> sorted_arr.(index_arr.(x)) <- x; index_arr.(x) <- index_arr.(x) + 1) arr;
sorted_arr
```

Here, `arr`

is the input array to be sorted. The function `counting_sort`

first finds the maximum value in the input array and creates a new array `count_arr`

to count the number of occurrences of each element in the input array. It then creates another array `index_arr`

to store the index of each element in the sorted output array. The function `fill_index_arr`

is a helper function that fills in the `index_arr`

array based on the counts in `count_arr`

. Finally, the function creates a new array `sorted_arr`

and fills it in by iterating over the input array and using the `index_arr`

array to determine the position of each element in the sorted output array.

```
let arr = [|5; 2; 9; 3; 6|]
let sorted_arr = counting_sort arr
let () = Array.iter (Printf.printf "%d ") sorted_arr
```

## Step-by-step Explanation

- Find the maximum value in the input array.
- Create a new array
`count_arr`

of length`max_val + 1`

and initialize all elements to 0. - Iterate over the input array and increment the count of each element in
`count_arr`

. - Create a new array
`index_arr`

of length`max_val + 1`

and initialize all elements to 0. - Define a helper function
`fill_index_arr`

that fills in the`index_arr`

array based on the counts in`count_arr`

. The function takes two arguments:`i`

and`j`

, where`i`

is the current index in`count_arr`

and`j`

is the current index in`index_arr`

. - Call the
`fill_index_arr`

function with initial arguments`0`

and`0`

. - Create a new array
`sorted_arr`

of length`n`

, where`n`

is the length of the input array. - Iterate over the input array and use the
`index_arr`

array to determine the position of each element in the sorted output array. Store each element in the corresponding position in`sorted_arr`

. - Return
`sorted_arr`

.

## Complexity Analysis

The time complexity of counting sort is O(n + k), where n is the length of the input array and k is the range of the input integers. The space complexity is also O(n + k).

The algorithm iterates over the input array twice: once to count the occurrences of each element and once to fill in the sorted output array. The time complexity of these two iterations is O(n). The algorithm also creates two additional arrays: `count_arr`

and `index_arr`

, each of length k. Therefore, the space complexity of the algorithm is O(n + k).