\
home Home
sort Sorts
Bubble Sort Selection Sort Insertion Sort
SORTING VISUALIZER - COUNTING SORT

  CountingSort(A[],n)

    1.   Initialize count array C[k]
        where k=maxele(A)

    2.   For j = 0 to n - 1

    3.     do C[A[j]]=C[A[j]]+1

    4.   For j = 1 to k

    5.     do C[j] += C[j-1]

    6.   For j = n-1 to 0

    7.     B[C[A[j]]-1] = A[j]

    8.     C[A[j]] -= 1

   
         

Complexity

Time
 Space
Best Case Average Case Worst Case
O(k)
O(n+k)
O(n+k)
O(n+k)

Counting Sort

What is the working mechanism of Counting Sort, and what is the origin of its name?

Counting sort is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (a kind of hashing). Then do some arithmetic operations to calculate the position of each object in the output sequence.


Is counting sort a stable, in-place sorting algorithm or an out-of-place sorting algorithm?

Counting sort is a stable out-of-place algorithm, meaning that it require extra space and maintains the relative order of duplicates.


How does the number of elements impact the efficiency of Counting sort?

Counting sort algorithm work best if k is not significantly larger than n. In this case the complexity becomes close to O(n) or linear.

What are advantages and disadvantages of Counting Sort?

Advantages:

  • Counting sort generally performs faster than all comparison-based sorting algorithms, such as merge sort and quicksort, if the range of input is of the order of the number of input.
  • Counting sort is easy to code.

Disadvantages:
  • Counting sort doesn't work on decimal values.
  • Counting sort is inefficient if the range of values to be sorted is very large.