Counting Sort Sequential vs Parallel

Counting sort is an efficient algorithm for sorting an array of elements that each have a nonnegative integer key, for example, an array, sometimes called a list, of positive integers could have keys that are just the value of the integer as the key, or a list of words could have keys assigned to them by some scheme mapping the alphabet to integers (to sort in alphabetical order, for instance). Unlike other sorting algorithms, such as mergesort, counting sort is an integer sorting algorithm, not a comparison based algorithm.

The complexity of the algorithm is Theta(n).

*An algorithm that maps the following input/output pair is called a sorting algorithm: *

Counting Sort Sequential

Counting sort assumes that each of the n input elements in a list has a key value ranging from 0 to k, for some integer k. For each element in the list, counting sort determines the number of elements that are less than it. Counting sort can use this information to place the element directly into the correct slot of the output array.

Counting sort uses three lists:


Counting Sort

Counting Sort Parallel

Bsed on the idea of sequential counting sort. Uses n^2 processors on a mesh grid of n x n. Running time complexity O(logn).

Counting Sort