XOR-Sort: A Combinatorial Algorithmic Approac...

XOR-Sort: A Combinatorial Algorithmic Approach

Author Name : Debashis Roy, Monodeep Banerjee

ABSTRACT

In this paper, a non-comparison type sorting algorithm namely XOR-sort, based on a hashing concept is proposed which can sort non-linear data set with high efficiency having an overall time complexity O(n). Data are stored in different linked lists according to the number of bits in their binary representation with the help of ‘AND’ and ‘XOR’ operations. For storing the sorted data in each list, an array is used, which holds two parameters at each indexed position: one is sorted elements and the other is the frequency of occurrence.  In this sorting method along with sorting the elements, the frequency of each element is also counted simultaneously. For the large repeated data, the proposed method is compared with the existing sorting algorithms and the results indicated that the efficiency of the proposed method is higher than others.

Keywords: Combinatorics; Hashing; Linked list; XOR; Frequency of Elements; Non-Comparison Sort.