# Counting Sort

**Counting sort is a type of Linear Time Sort**

- Counting Sort was invented by H.H.Seward in 1954
- All the sorting algorithms introduced so far share an interesting property: the sorted order they determine is based only on comparison between the input elements

**Assumption of Counting Sort**

- Counting sort assumes that each of the element is an integer and lies in the range 1 to k, for some integer k
- When k=O(n) then sort runs in O(n) time.
- Determine how many elements are less than an element
*x* - Then place x directly on its correct position

**Running Time**

- T(n) = O(k) + O(n) + O(k) + O(n)

= O(k+n+k+n) = O(2k + 2n)

Assumption: k is O(n)

Hence T(n) = O(n)

Thus Counting Sort beats the running time of “nlogn” as it is not a comparison based sort

Related links

Single link list Stack AVL Trees Binary search Counting Sort

Doubly link list Queue Graphs Bubble Sort Radix sort

Circular link list Binary search tree Hashing Insertion Sort Bucket Sort

Josephus Problem Tree Traversal Heaps Quick Sort Merge Sort

## At Cui tutorial, courses, past papers and final year projects

#tutorial #cui #pastpaper #courses #finalyearproject