Shell Sort

Written By Hadron DaVinci

Shell Sort Animation



Shell Sort Infographic

Methodology

Shell Sort is a hybrid sorting algorithm based on Insertion Sort.

Setup:

  • Let Gap Size (GS) be initial number of elements

Repeat while GS >= 1:

  • Update GS

    • GS = floor(GS / 2)

  • Select indices by skipping GS elements

  • Insert Sort elements at selected indices


Complexity

Time Complexity (Worst): N^2

Time Complexity (Best): N log(N)

Space Complexity: 1

Unstable

Download Source Code
Hadron DaVinci https://hadrondavinci.com
Next

Comb Sort