K-Index-Sort: Sorting Unique Integer in Linear Time
H. M. Kamal,
Zia Uddin Ahamed Khan
Mohammad Khairul Islam
This paper deals with sorting a list of items. Sorting within a linear time is always desirable. We have many sorting algorithms. But the complexities of almost all of them are not linear. Here we have proposed a sorting algorithm named K-Index-Sort whose time complexity is O(n). We have used a temporary character array that will hold a track character against every input number. This is an interesting thing of that method as the input list is being sorted with the help of a character array. For every input k, a track symbol (like ‘-‘, ‘$`, ‘#`, any symbol) is placed to that character array to an index of k. After collecting the index numbers sequentially from that where the track symbol is residing we will get sorted list. Distinct integer numbers are a prerequisite of that algorithm. This algorithm will perform better performance for k=O(n) where k is the maximum number and n is the number of input items.