Shell Sort is an optimization of Insertion Sort that sorts elements separated by decreasing gap values, allowing the array to become partially sorted before the final insertion sort pass.

What is the time complexity of Shell Sort?

The time complexity of Shell Sort depends on the gap sequence used. Common implementations achieve approximately O(n log² n) average performance, while the worst case can be O(n²).

Is Shell Sort stable?

No. Shell Sort is not a stable sorting algorithm because equal elements may change their relative order during the gap-based sorting process.

Is Shell Sort an in-place algorithm?

Yes. Shell Sort is an in-place sorting algorithm that requires only O(1) additional memory.

Why should I learn Shell Sort?

Shell Sort demonstrates how simple improvements to Insertion Sort can significantly enhance performance. It introduces the concept of gap sequences and serves as a practical bridge between elementary and advanced sorting algorithms.

Playground Component

Shell Sort
Visualizer

An interactive Shell Sort visualization built with HTML, CSS, and JavaScript. Watch how the algorithm sorts elements using decreasing gap sizes before performing a final insertion sort, with adjustable animation speed.

Shell Sort Visualizer

Copy Code


  
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title> Sort Visualizer</title>

<!-- <link href="https://fonts.googleapis.com/css2?family=Poppins:wght@400;500;600;700&display=swap" rel="stylesheet"> -->

<style>
*{
    margin:0;
    padding:0;
    box-sizing:border-box;
}

:root{
    --bg:#090909;
    --panel:#111111;
    --panel2:#171717;
    --gold:#f4c430;
    --gold2:#ffd54d;
    --border:#3a2d08;
    --text:#f5f5f5;
}

body{
    font-family:'Poppins',sans-serif;
    background:
        radial-gradient(circle at top,#1b1606 0%,#090909 35%),
        var(--bg);
    color:var(--text);
    min-height:100vh;
    display:flex;
    flex-direction:column;
    align-items:center;
    padding:40px 25px;
}

h1{
    font-size:3rem;
    font-weight:700;
    color:var(--gold);
    margin-bottom:30px;
    text-shadow:0 0 18px rgba(244,196,48,.18);
    letter-spacing:.5px;
}

.controls{
    display:flex;
    gap:18px;
    flex-wrap:wrap;
    justify-content:center;
    margin-bottom:35px;
}

button{
    min-width:170px;
    padding:15px 22px;
    font-size:17px;
    font-weight:600;
    border-radius:14px;
    border:1px solid #705510;
    background:linear-gradient(180deg,#ffd54d,#e7b817);
    color:#121212;
    cursor:pointer;
    transition:.28s;
    box-shadow:
        0 8px 20px rgba(0,0,0,.45),
        inset 0 1px 0 rgba(255,255,255,.35);
}

button:hover{
    transform:translateY(-3px);
    box-shadow:
        0 14px 30px rgba(244,196,48,.22),
        inset 0 1px 0 rgba(255,255,255,.4);
}

button:active{
    transform:scale(.98);
}

#container{
    width:min(94%,1300px);
    height:590px;
    background:linear-gradient(180deg,#121212,#0b0b0b);
    border:1px solid var(--border);
    border-radius:24px;
    display:flex;
    align-items:flex-end;
    justify-content:center;
    gap:4px;
    padding:16px;
    box-shadow:
        0 20px 45px rgba(0,0,0,.55),
        inset 0 0 0 1px rgba(255,255,255,.03),
        0 0 35px rgba(244,196,48,.06);
    position:relative;
    overflow:hidden;
}

#container::before{
    content:"";
    position:absolute;
    inset:0;
    pointer-events:none;
    background:
        linear-gradient(rgba(255,255,255,.03) 1px,transparent 1px);
    background-size:100% 60px;
    opacity:.35;
}

.bar{
    width:12px;
    background:linear-gradient(to top,#b88700,#ffd54d);
    border-radius:4px 4px 0 0;
    transition:
        height linear,
        background .2s linear,
        transform .15s linear;
    box-shadow:0 0 10px rgba(244,196,48,.15);
    z-index:1;
}

@media(max-width:900px){
    h1{
        font-size:2.2rem;
    }

    button{
        min-width:145px;
        font-size:15px;
    }

    #container{
        height:470px;
    }

    .bar{
        width:8px;
        gap:2px;
    }
}
</style>
</head>

<body>

<h1>Shell Sort Visualizer</h1>

<div class="controls">
    <button onclick="randomize()">Randomize</button>
    <button onclick="shellSort()">Sort</button>
    <button id="speedBtn" onclick="toggleSpeed()">Speed: Normal</button>
</div>

<div id="container"></div>

<script>

let sorting = false;

const speedLevels = [
    { name: "Very Slow", delay: 500 },
    { name: "Slow", delay: 120 },
    { name: "Normal", delay: 70 },
    { name: "Fast", delay: 35 },
    { name: "Very Fast", delay: 1 }
];

let speedIndex = 2;
let speed = speedLevels[speedIndex].delay;

const container = document.getElementById("container");

let values=[];

function toggleSpeed() {
    speedIndex++;
    if (speedIndex >= speedLevels.length) speedIndex = 0;
    speed = speedLevels[speedIndex].delay;
    document.getElementById("speedBtn").textContent =
        "Speed: " + speedLevels[speedIndex].name;
}

function createBars(){
    container.innerHTML="";
    values.forEach(v=>{
        const bar=document.createElement("div");
        bar.className="bar";
        bar.style.height=v+"px";
        container.appendChild(bar);
    });
}

function randomize(){
    values=[];
    for(let i=0;i<100;i++){
        values.push(Math.floor(Math.random()*350)+30);
    }
    createBars();
}

function sleep(ms){
    return new Promise(resolve=>setTimeout(resolve,ms));
}
async function shellSort() {
    if (sorting) return;
    sorting = true;

    const bars = document.getElementsByClassName("bar");
    let n = values.length;

    // Start with a large gap, then reduce it
    for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {

        for (let i = gap; i < n; i++) {

            let temp = values[i];
            let j = i;

            // Current element
            bars[i].style.background = "#9c27b0";
            await sleep(speed);

            while (j >= gap && values[j - gap] > temp) {

                // Comparing element
                bars[j - gap].style.background = "#ff3b30";
                await sleep(speed);

                values[j] = values[j - gap];
                bars[j].style.height = values[j] + "px";

                bars[j].style.background = "#ff9800";

                await sleep(speed);

                bars[j - gap].style.background =
                    "linear-gradient(to top,#b88700,#ffd54d)";
                bars[j].style.background =
                    "linear-gradient(to top,#b88700,#ffd54d)";

                j -= gap;
            }

            values[j] = temp;
            bars[j].style.height = temp + "px";

            bars[j].style.background = "#00bcd4";
            await sleep(speed);

            bars[j].style.background =
                "linear-gradient(to top,#b88700,#ffd54d)";
        }
    }

    // Final coloring
    for (let i = 0; i < n; i++) {
        bars[i].style.background = "#39d353";
        await sleep(5);
    }

    sorting = false;
}

randomize();

</script>

</body>
</html>

About this Component

Shell Sort is an optimization of Insertion Sort that improves performance by comparing and sorting elements that are far apart before gradually reducing the gap between them. As the gap decreases, the array becomes increasingly ordered, making the final insertion sort pass highly efficient. This interactive visualization lets you observe how the gap sequence changes over time, how elements are compared across larger distances, and how the array gradually becomes sorted. You can randomize the array, adjust the animation speed, and watch every comparison and movement step by step. Shell Sort has a time complexity that depends on the chosen gap sequence. In practice, it performs much better than simple insertion sort, with common implementations achieving around O(n log² n) average performance. It is an in-place algorithm but is not stable because equal elements may change their relative order during sorting.