What is the time complexity of shell sort?

Best case O(n log n). Average case depends on the gaps. Worst case O(n²). Space complexity is O(1). Knuth's 3k+1 sequence gives O(n^1.5); the optimal sequence is unknown.

Shell sort

medium

Sort elements that are `gap` apart first, so a badly-placed value jumps most of the distance in one hop, then finish with a gap of 1 on data that is now nearly ordered. The gap sequence is the whole algorithm.

Best O(n log n)Average depends on the gapsWorst O(n²)Space O(1)Not stableIn place

Loading the shell sort engine…

Where to go next

Insertion sort

easy

How you sort a hand of cards.

Quick sort

medium

Partition around a pivot, then recurse on both halves.

Heap sort

medium

Build a heap in the array, then extract the maximum n times.