Shell Sort Algorithm

Shell Sort algorithm, also known as the diminishing increment sort, is an in-place comparison-based sorting algorithm that generalizes the insertion sort method. It was invented by Donald Shell in 1959, and it works by comparing elements separated by a certain "gap" and swapping them if they are in the wrong order. The process is repeated with progressively smaller gaps until the list is sorted. The gap sequence is crucial in determining the algorithm's efficiency, with different sequences producing varying results. Some popular gap sequences include Shell's original sequence (N/2, N/4, ..., 1) and the more efficient Ciura sequence. The primary advantage of the Shell Sort algorithm is its improved performance over the basic insertion sort, especially for larger datasets. The reason for this improvement is that it allows for more significant movements of elements earlier in the sorting process, reducing the number of required swaps. While it is not as fast as more advanced sorting algorithms like quicksort or merge sort, it has a straightforward implementation and requires less memory. The Shell Sort algorithm is best suited for situations where simplicity and lower memory usage are more critical than achieving the best possible performance.
fun MutableList<Int>.swap(index1: Int, index2: Int) {
    val tmp = this[index1]
    this[index1] = this[index2]
    this[index2] = tmp
}

fun MutableList<Int>.shellSort(): MutableList<Int> {

    var sublistCount = count() / 2

    while (sublistCount > 0) {

        var index = 0
        outer@while (index >= 0 && index < count()) {

            if (index + sublistCount >= count()) break

            if (this[index] > this[index + sublistCount]) {
                swap(index, index + sublistCount)
            }

            if (sublistCount == 1 && index > 0) {
                while (this[index - 1] > this[index] && index - 1 > 0) {
                    swap(index - 1, index)
                    index -= 1
                }
                index++
            } else {
                index++
                continue@outer
            }
        }

        sublistCount /= 2
    }

    return this
}

fun main(args: Array<String>) {
    var mutableListOfInt = mutableListOf(10, 4, 5, 2, 1, 3, 6, 9, 8, 7)

    print(mutableListOfInt.shellSort().toString())
}

LANGUAGE:

DARK MODE: