Visualizing the Shell Sort algorithm in Flutter

1. What Is Shell Sort?

Shell Sort is an in-place comparison-based sorting algorithm that generalizes Insertion Sort to allow the exchange of far-apart elements. It was developed by Donald Shell in 1959 and is notable for being the first algorithm to break the O(n²) time barrier.

It works faster than Bubble, Insertion, and Selection sorts, especially for medium-sized datasets.

2. How Shell Sort Works

Shell Sort introduces the concept of gaps. Instead of comparing adjacent elements (like in Insertion Sort), it compares elements that are far apart.

Basic Steps:

Start with a large gap (usually n/2).
Perform insertion sort on elements that are gap distance apart.
Gradually reduce the gap and repeat.
End when gap = 1 → final pass is a simple insertion sort.

The idea is that by first sorting elements far apart, we reduce large disorder quickly, so less work is needed when the gap becomes smaller.

3. Shell Sort Pseudocode

function shellSort(array):
    n = length(array)
    gap = n // 2
    while gap > 0:
        for i from gap to n - 1:
            temp = array[i]
            j = i
            while j >= gap and array[j - gap] > temp:
                array[j] = array[j - gap]
                j = j - gap
            array[j] = temp
        gap = gap // 2

4. Step-by-Step Example

Sort [9, 8, 3, 7, 5, 6, 4, 1]

Step 1: gap = 4

Compare and sort pairs 0↔4, 1↔5, 2↔6, 3↔7
Array becomes: [5, 6, 3, 1, 9, 8, 4, 7]

Step 2: gap = 2

Compare and sort 0↔2↔4↔6 and 1↔3↔5↔7
After rearranging: [3, 1, 4, 6, 5, 7, 9, 8]

Step 3: gap = 1

Final insertion sort pass
Sorted array: [1, 3, 4, 5, 6, 7, 8, 9]

5. Time and Space Complexity

Case	Time Complexity
Best	O(n log n)
Average	O(n log² n) to O(n¹.⁵)
Worst	O(n²)

Depends on the gap sequence. Shell’s original sequence has O(n²), but modern variants (like Hibbard or Sedgewick gaps) are much faster.

Space Complexity: O(1)
Stable Sort: No

6. Shell Sort in Dart (Flutter-Friendly)

Future<void> shellSort(List<int> array, Function(List<int>) onUpdate) async {
  int n = array.length;

  for (int gap = n ~/ 2; gap > 0; gap ~/= 2) {
    for (int i = gap; i < n; i++) {
      int temp = array[i];
      int j = i;
      while (j >= gap && array[j - gap] > temp) {
        array[j] = array[j - gap];
        j -= gap;
        onUpdate(List.from(array));
        await Future.delayed(Duration(milliseconds: 300));
      }
      array[j] = temp;
      onUpdate(List.from(array));
      await Future.delayed(Duration(milliseconds: 300));
    }
  }
}

This animation shows long-range swaps at first, gradually zooming into local correction as the gap narrows — great for visual learners.

7. Visualization with Flutter + CustomPaint

With CustomPaint, you can:

Use color gradients to highlight gaps.
Animate far-apart comparisons → visually shows the transition from disorder to order.
Draw gap lines or brackets across the bars.
Highlight the element being inserted and those being shifted.

It’s one of the most visually insightful algorithms in the series.

8. When Should You Use Shell Sort?

Use Shell Sort when:

You want a simple, space-efficient, yet reasonably fast algorithm.
You need better performance than basic O(n²) sorts but don’t want the complexity of Merge/Quick Sort.
Stability isn’t required.

9. Summary

Shell Sort is a historic breakthrough that inspired faster sorts. It extends Insertion Sort’s power using gap-based comparison, performing well for medium-sized or semi-sorted data.

Coming up next in our sorting adventure: Intro Sort — the intelligent hybrid that starts with QuickSort but switches when needed!