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:

- 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 = [];
```

- 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
```

- 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
```

- 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]
```

- 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 -

https://www.cs.usfca.edu/~galles/visualization/RadixSort.html - Very useful animation about radix sort

https://www.w3resource.com/javascript-exercises/searching-and-sorting-algorithm/searching-and-sorting-algorithm-exercise-11.php - Information about how to format a counting sort in javascript

## Top comments (0)