Shell Sort

How to use ?

Enter an array separated by commas as : 16,15,15,10,1 or just press the hand icon to generate a random array then press enter or Sort button. Sorting will start and you can watch each pass as it gets sorted. When it shows green it means the two of them are being compared when red shows, it means the left number is greater than right number so it needs swapping The blue color means the number is at its correct position and thus sorted it will continue to check other numbers until it reaches end.

Shell Sort Overview

History

Shell sort was proposed by Donald Shell in 1959 as a generalization of insertion sort. It improves upon the insertion sort algorithm by allowing the exchange of items that are far apart, making it more efficient for larger datasets.

Current Uses

Intermediate Sorting: Used as an intermediate sort for larger datasets.
Small to Medium Datasets: Effective for small to medium-sized datasets where performance is essential.
Hybrid Algorithms: Often used in combination with other sorting algorithms to enhance performance.

Time and Space Complexity

Time Complexity

Best Case: O(n log n) – Efficient for certain sequences.
Average Case: O(n^3/2) – Dependent on the gap sequence used.
Worst Case: O(n²) – Similar to insertion sort for certain gap sequences.

Space Complexity

Space Complexity: O(1) – It is an in-place sorting algorithm requiring minimal additional space.

Pseudo Code

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

Key Characteristics

In-Place: Shell sort requires minimal additional memory.
Not Stable: The algorithm is not stable as it may change the relative order of equal elements.

Summary

Shell sort is an efficient generalization of insertion sort that enhances performance through the use of gaps. With a time complexity that varies based on the gap sequence, it is particularly effective for small to medium datasets.

Shell Sort Code Implementation