Skip to main content

Rank Sort

Rank Sort is an algorithm for sorting a vector based on the rank of each element in the vector. The rank of an element represents how many numbers in the vector are smaller than it.

Steps:

  • Calculate the rank of each element: for each element in the vector v[i], where 0 ⇐ i < N (N - the size of the vector), count how many elements in the vector v[j], j != i, are smaller: v[j] < v[i], 0 ⇐ i, j < N, i != j.

  • The element at position "i" will be at position "rank" in the new sorted vector: q[rank] = v[i].

Pseudocod serial:

for i = 0 to N
    for j = 0 to N
	if v[i] > v[j]
		rank[i]++

for i = 0 to N
    results[rank[i]] = v[i]

The "Parallel Rank Sort" algorithm aims to parallelize step 1. The rank of each element can be calculated in parallel, meaning each process or thread will compute ranks for the elements within its interval: [start, end).

The time complexity of the algorithm is O(n^2), which makes the complexity for parallelizing step 1 become O(n^2 / p), where p is the number of processors/threads.

Here are attached slides that illustrate step by step: slides