# Simple Counting Sort

So, why does counting sort have a different time complexity than the merge, bubble, heap and other sorts, why is there a variable k in the time complexity?

``````countingSort([9,1,0,4,6,5,7,8,1,3,2,3,3])

function countingSort(arrayToSort) {

// 1.
let i;
let indexOfReturn = 0;
let count = [];

// 2.
for (i = 0; i <= 9; i++) {
count[i] = 0;
}

// 3.
for (i = 0; i < arrayToSort.length; i++) {
count[arr[i]]++;
}

// 4.
for (i = 0; i <= 9; i++) {
while (count[i]-- > 0) {
arrayToSort[indexOfReturn++] = i;
}
}
return arrayToSort;
}

//output => [0,1,1,2,3,3,3,4,5,6,7,8,9]
``````

This is complicated so let's break it down into 4 components:

1. Variables needed
``````//We are using a base 10 counting sort so the minimum
//digit is 0 and the maximum digit is 9

//declaring i for index as a let to use in our for loops
let i;

//declaring the starting index of the returnArray,
//which will just be a modification of the ArrayToSort
let indexOfReturn = 0;

//count is an array which will be marked in the time complexity
//as k so when you see O(n+k) k is the length(and therefore operations)
//of count and n is the length(and therefore operations)
//of the array to be sorted
let count = [];

``````
1. First counting length for() loop
``````for (i = 0; i <= 9; i++) {
count[i] = 0;
}

//this for loop sets up the count array to be used to
//keep track of the count of all numbers in the array to be sorted
// => count = [0,0,0,0,0,0,0,0,0,0]
//when created the count array has indexes equal to the base of the
//numbers that you are sorting, and because we are sorting in base 10
//it has 10 indexes that all point to the value zero
``````
1. First array length for() loop
``````for (i = 0; i < arrayToSort.length; i++) {
count[arr[i]]++;
}

//this for loop goes for the length of the array that will be
//sorted and increases the value in the indexes of count that are
//equal to the value in the array that needs to be sorted
// => count = [1,2,1,3,1,1,1,1,1,1]
//the indexes of count now reference the amount of each digit that
//are in the array
``````
1. Second counting length for() loop
``````for (i = 0; i <= 9; i++) {
while (count[i]-- > 0) {
arrayToSort[indexOfReturn++] = i;
}
}
//this for loop goes for the length of the count and changes the indexes
//of the array to be sorted to be equal to the index of the count array
//while the count is still greater than 0
//You can see that the indexes are not compared against each other but
//are instead just kept track of through count and returned in index
//order from smallest to largest from 0 -> 9
// => arrayToSort = [0,1,1,2,3,3,3,4,5,6,7,8,9]
``````
1. Pulling it all together again
``````countingSort([9,1,0,4,6,5,7,8,1,3,2,3,3])

function countingSort(arrayToSort) {
let i;
let indexOfReturn = 0;
let count = [];
for (i = 0; i <= 9; i++) {
count[i] = 0;
}
for (i = 0; i < arrayToSort.length; i++) {
count[arr[i]]++;
}
for (i = 0; i <= 9; i++) {
while (count[i]-- > 0) {
arrayToSort[indexOfReturn++] = i;
}
}
return arrayToSort;
}

//output => [0,1,1,2,3,3,3,4,5,6,7,8,9]

// after all the counting and indexing into count is done
//the return is the sorted array
``````

Counting sort doesn't seem too useful but radix sort is built off of counting sorts and both Counting sort and Radix sort have time complexities based off of

``````
// n => Length of the array
// k => Base of the number system you are sorting
// Leading to O ( n + k ) being the runtime

``````

Counting sort has low time complexity because it has limited use, it can only be used on numbers of one character length. It is not a comparison sort so you don't need to know the values of the indexes next to what you are sorting.

References -   