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 sorting_shell_sort:
    def sort(self, nums: list[int]) -> list[int]:
        # Start by comparing values that are far apart.
        gap = len(nums) // 2

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

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

                nums[j + gap] = val

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

        return nums