Shell Sort

Algorithms

Shell sort is an optimization of insertion sort that allows the exchange of items that are far apart. It works by sorting elements at specific intervals, gradually reducing the interval size.

Algorithm

The algorithm starts by sorting pairs of elements far apart from each other, then progressively reduces the gap between elements to be compared. This allows elements to move to their correct positions faster than in insertion sort.

Time Complexity

The time complexity depends on the gap sequence used. With the gap sequence $n /2, n /4, ...$ , the worst-case time complexity is $O (n^{2})$ , but it often performs better in practice.

Implementation

def shell_sort(arr):
    n = len(arr)
    gap = n // 2

    while gap > 0:
        # Perform a gapped insertion sort
        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
        
        # Reduce the gap
        gap //= 2

    return arr

# Example usage with different numbers
arr = [45, 23, 78, 12, 56, 89, 34]
sorted_arr = shell_sort(arr)
print("Sorted array:", sorted_arr)