Shell Sort

Algorithm Steps

Choose an initial gap value (typically n/2) for the array of n elements.
For each gap, perform a gapped insertion sort: compare elements that are 'gap' positions apart and swap them if needed.
Reduce the gap value (commonly gap = gap/2) and repeat step 2.
Continue until the gap becomes 0, at which point the array is fully sorted.

Shell Sort Program Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2
    return arr

if __name__ == '__main__':
    arr = [6, 3, 8, 2, 7, 4]
    shell_sort(arr)
    print("Sorted array is:", arr)