WCSE

SONIK: Efficient In-Situ All Item Rank Generation Using Bit Operations

Abstract— Sorting, a classical combinatorial process, forms the bedrock of numerous algorithms with varied applications. A related problem involves efficiently finding the corresponding ranks of all the elements – catering to rank queries, data partitioning and allocation, etc. Although, the element ranks can be subsequently obtained by initially sorting the elements, such procedures involve O(n log n) computations and might not be suitable with large input sizes for hard real-time systems or for applications with data reordering constraints. This paper proposes SONIK, a non-comparison linear time and space algorithm using bit operations inspired by radix sort for computing the ranks of all input integer elements, providing implicit sorting. The element ranks are generated in-situ without re-ordering or using other sorting mechanism.

Index Terms— all item rank computation, integer sort, non-comparison sort, bit operations, linear time.

Sourav Dutta
Max Planck Institute for Informatics, GERMANY

[Download]