A new sort algorithm: Self-indexed sort

ABSTRACT: This paper presents a new sort algorithm, self-indexed sort (SIS), on an approach of non compare-based sorting. Results on time complexity O(n) and space complexity O(n+m) are achieved, where n is the size of data being sorted and m is the size of the sorting space. Two versions of SIS sort algorithm are implemented with one for the sort of structured records and the other for pure data file. The performance of SIS sort is tested and analysed under various conditions