Shell Sort Program with Explanation and Code

2025-11-19 shell sort gap sort insertion sort optimization algorithm programs sorting algorithms python shell sort c shell sort javascript shell sort php shell sort csharp shell sort data structures gap sequence sorting

Shell Sort is an efficient sorting algorithm that improves insertion sort by allowing element comparisons at larger gaps. This page includes a detailed explanation and full Shell Sort program examples in Python, C, JavaScript, PHP, and C#. Ideal for students and interview preparation.

Program Explanation

What is Shell Sort?

Shell Sort is an optimized version of Insertion Sort that allows the exchange of far-apart elements. It works by sorting elements at a specific gap, gradually reducing the gap until it becomes 1. When the gap is 1, the algorithm becomes normal insertion sort but with the list already partially sorted, improving performance.

Steps to Solve

  1. Start by choosing a large gap value (typically n/2).
  2. Perform gap-based insertion sort on elements that are gap distance apart.
  3. Reduce the gap gradually (example: gap = gap / 2).
  4. Repeat the sorting process for each gap value.
  5. Continue until the final gap becomes 1.
  6. Perform a final insertion sort pass when gap = 1.
  7. The array becomes fully sorted as the gap reduces.

Key Points

  • Improves insertion sort performance significantly.
  • Not a stable sorting algorithm.
  • Time complexity varies based on gap sequence; best sequences give near O(n log n).
  • Works in-place, requiring no extra space.
  • Efficient for medium and large datasets.
  • Common gap sequences: Shell’s original, Hibbard, Knuth, Sedgewick.

Program Code


def shell_sort(arr):
    n = len(arr)
    gap = n // 2

    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i

            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap

            arr[j] = temp

        gap //= 2

arr = list(map(int, input("Enter numbers: ").split()))
shell_sort(arr)
print("Sorted array:", arr)
      

#include <stdio.h>

void shellSort(int arr[], int n) {
    for (int gap = n/2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j = i;

            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }

            arr[j] = temp;
        }
    }
}

int main() {
    int n;
    printf("Enter number of elements: ");
    scanf("%d", &n);

    int arr[n];
    printf("Enter elements: ");
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    shellSort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}
      

function shellSort(arr) {
  let n = arr.length;
  let gap = Math.floor(n / 2);

  while (gap > 0) {
    for (let i = gap; i < n; i++) {
      let temp = arr[i];
      let j = i;

      while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap];
        j -= gap;
      }

      arr[j] = temp;
    }

    gap = Math.floor(gap / 2);
  }
}

let arr = prompt("Enter numbers:").split(" ").map(Number);
shellSort(arr);
console.log("Sorted array:", arr);
      

using System;

class Program {

    static void ShellSort(int[] arr) {
        int n = arr.Length;

        for (int gap = n/2; gap > 0; gap /= 2) {
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j = i;

                while (j >= gap && arr[j - gap] > temp) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }

                arr[j] = temp;
            }
        }
    }

    static void Main() {
        Console.Write("Enter numbers: ");
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

        ShellSort(arr);

        Console.Write("Sorted array: ");
        foreach (int x in arr)
            Console.Write(x + " ");
    }
}
      

<?php

function shellSort(&$arr) {
    $n = count($arr);
    $gap = intdiv($n, 2);

    while ($gap > 0) {
        for ($i = $gap; $i < $n; $i++) {
            $temp = $arr[$i];
            $j = $i;

            while ($j >= $gap && $arr[$j - $gap] > $temp) {
                $arr[$j] = $arr[$j - $gap];
                $j -= $gap;
            }

            $arr[$j] = $temp;
        }
        $gap = intdiv($gap, 2);
    }
}

$arr = array_map('intval', explode(" ", readline("Enter numbers: ")));
shellSort($arr);

echo "Sorted array: " . implode(" ", $arr);

?>
1