Shell Sort

Implement Shell sort with a shrinking gap sequence and return the sorted list.

sorting shell-sort in-place algorithms

Write a function `shell_sort(arr: list) -> list` that sorts a list of integers in ascending order **in-place** using Shell sort and returns the same list.

Implement the classic Shell sort algorithm:
1. Start with a gap `g` equal to `len(arr) // 2`.
2. While `g > 0`, perform a **gapped insertion sort**: for each index `i` from `g` to `len(arr)-1`, temporarily store `arr[i]`, then shift elements `arr[i-g]`, `arr[i-2g]`, ... that are greater than the stored value to the right by `g`, and insert the stored value into the correct position.
3. After completing all positions for a given gap, divide the gap by 2 (integer division) and repeat.
4. Continue until the gap becomes 0.

The function must modify the original list in-place and return it. Do not use built-in sorting methods (e.g., `list.sort` or `sorted`) or any other sorting algorithm.

Hints:
- The gap sequence is simply `n//2, n//4, n//8, ...` until 1.
- The inner loop is similar to insertion sort but with step `g`.

Constraints

The input list `arr` may contain any integers (including negatives and duplicates). Its length `n` satisfies `0 <= n <= 10^4`. The algorithm should run in O(n log n) average time (using the halving gap sequence) and O(1) extra space.

Example

>>> shell_sort([4, 3, 2, 1])
[1, 2, 3, 4]
>>> shell_sort([5, 2, 9, 1, 5, 6])
[1, 2, 5, 5, 6, 9]
>>> shell_sort([])
[]
>>> arr = [3, 0, -1]
>>> result = shell_sort(arr)
>>> result is arr
True

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use `g = len(arr) // 2` and loop while `g > 0`.

In each pass, for `i` from `g` to `n-1`, save `arr[i]` and shift larger elements backward by `g`.

After each pass, set `g //= 2`.

Return the same list object after sorting.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.