Shell sort

Problem¶

Implement Shell sort for a Python list.

Key trick¶

Run insertion sort over progressively smaller gaps until the final gap is one.

Shell sort is inappropriate for linked lists because gap-based access requires repeated traversal.

Trap¶

Its complexity depends on the gap sequence; claiming unconditional \(O(n \log n)\) is incorrect.

Why is it interesting?¶

It improves insertion sort by moving distant elements early while retaining \(O(1)\) auxiliary space.

Python solution¶

class sort_shell_sort:
    def sort(self, nums: list[int]) -> list[int]:
        # Preserve the caller's input.
        arr = nums[:]

        # Start by comparing values that are far apart.
        gap = len(arr) // 2

        while gap > 0:
            # Perform insertion sort independently on each gap-separated group.
            for i in range(gap, len(arr)):
                val = arr[i]
                j = i

                # Shift larger values by one gap instead of one position.
                while j >= gap and arr[j - gap] > val:
                    arr[j] = arr[j - gap]
                    j -= gap

                arr[j] = val

            # The final gap of one is ordinary insertion sort.
            gap //= 2

        return arr