Skip (Insertion) Sort, Skip List Based New and Very Efficient Sorting Algorithm

The aim of this paper is to propose a new sorting algorithm based on skip list. The proposed sorting algorithm has similar/same logic with skip list, due to this case, it was called as SkipSort algorithm. While sorting data, each element is located in its position in a pyramidal way and this position is the required position of element in the sorted array. The locating time of each element is O(N), when there are N elements in unsorted set. Thus, the time complexity of a set of size N will be O(NlgN). The proposed algorithm was applied to a randomly generated set, and the obtained results are superior to the results of sorting algorithms HeapSort, MergeSort, etc. The same case is also valid for sorted set or sorted in descending order set. The performance of the proposed algorithm in sorted or sorted in descending order is better than performance of random case approximately 1.5-2 times.