ANALYSIS OF SHELLSORT ALGORITHMS
Avik Mitra · International Journal of Advanced Research in Computer Science · 2019
Shellsort is a comparison sort that uses insertion sort at each iteration to make a list of interleaved elements nearly sorted so that at the last iteration the list is almost sorted. The time complexity of Shellsort is dependent upon the method of interleaving (called increment sequence) giving variants of Shellsort. However, the problem of finding proper interleaving to achieve the minimum time complexity of O(n log n) is still open. In this paper, we have analyzed the performance of variants of Shellsort based on their time complexity. Our measure of time complexity is independent of the machine configuration and considers all the operations of a sorting process. We found that the interleaving method or increment sequence proposed by Sedgewick performs best among the analyzed variants.