Rank sort

Rank sort

Class	Sorting algorithm
Data structure	Array
Worst-case performance	$O(n^2)$ comparisons
Best-case performance	$O(n^2)$ comparisons
Average performance	$O(n^2)$ comparisons
Worst-case space complexity	$O(n)$ total, $O(n)$ auxiliary

In computer science, rank sort (or enumeration sort ) is an algorithm for sorting a collection of objects by counting for each object the number of objects in the collection that are smaller than it, allowing one to deduce the rank of the object in the sorted array.

Pseudocode

In pseudocode, the algorithm may be expressed as:

function RankSort(input) is
    
    rank ← array of same length as input, initialized with zeroes
    output ← array of same length as input
    
    for i = 0 to length(input) - 1 do
        for j = 0 to length(input) - 1 do
            if input[j] < input[i] then
                rank[i] = rank[i] + 1

    for i = 0 to length(input) - 1 do
        r = rank[i]
        output[r] = input[i]

    return output

Where input is the array to be sorted, rank is an auxiliary array used to store the rank of each items and output is the sorted output array.

As stated, the algorithm works only if all items are different. In case of an array with identical elements, the algorithm can be modified to accord for it, by counting also identical elements with an index smaller than it.

References

This article "Rank sort" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Rank sort. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

---