Shell Sort

Shell sort, also known as diminishing increment sort, is an in-place comparison-based sorting algorithm. It is an extension of insertion sort where the elements are h-sorted, which means that every h-th element (starting from the first element) is sorted. The value of h is called the gap or increment sequence.

The main idea behind shell sort is to improve upon the insertion sort algorithm by allowing elements to move more than one position at a time towards their sorted position. This helps to reduce the total number of comparisons and exchanges required to sort the array, especially when dealing with larger arrays.

Here's how the shell sort algorithm works:

Choose Increment Sequence: Select an increment sequence that determines the gap between elements to be compared and swapped during each pass of the algorithm. Commonly used increment sequences include the original sequence proposed by Shell (e.g., n/2, n/4, n/8, ..., 1) or other sequences such as Hibbard's sequence or Sedgewick's sequence.

Gap Sorting: Starting with the first element, compare and swap elements that are h positions apart, where h is the current increment value. This process is repeated for each increment value in the sequence until the increment value is 1, at which point the array is sorted using regular insertion sort.

Reduce Increment: After each pass through the array, reduce the increment value until it becomes 1, indicating the final pass where the array is sorted using regular insertion sort.

Algorithm for: Gap Sequence

FUNCTION shell_sort_gap(n)
// Calculates the gap sequence for Shell sort
// Input: The length of the array n
// Output: List containing the gap sequence

    // Start with an initial gap value
    gap = n / 2
    // Create an empty list to store the gap sequence
    gap_sequence = []
    
    // While the gap value is greater than 0
    WHILE gap > 0 DO
        // Append the current gap value to the gap sequence
        gap_sequence.append(gap)
        // Reduce the gap value by half
        gap = gap / 2
    END WHILE
    
    // Return the gap sequence list
    RETURN gap_sequence
END FUNCTION

Algorithm for Shell sort

FUNCTION ShellSort(A[0..n - 1])
// Sorts the array A[0..n - 1] using Shell sort
// Input: An array A[0..n - 1] of orderable elements
// Output: Array A[0..n - 1] sorted in nondecreasing order

    // Calculate the gap sequence for Shell sort
    gap_sequence = shell_sort_gap(n)
    
    // Iterate over each gap in the gap sequence
    FOR EACH gap IN gap_sequence DO
        // Perform insertion sort with the current gap
        FOR i = gap TO n - 1 DO
            // Set the key element
            key = A[i]
            // Move elements of A[0..i - gap], A[1..i - gap + 1], ..., A[i - gap] that are greater than key to the right
            j = i
            WHILE j >= gap AND A[j - gap] > key DO
                A[j] = A[j - gap]
                j = j - gap
            END WHILE
            // Place the key element at its correct position
            A[j] = key
        END FOR
    END FOR
    
    // Return the sorted array A
    RETURN A
END FUNCTION

Shell  sort for the list = [8, 5, 10, 2, 7, 3] with starting gap size = 3 and reducing the gap size by 1 after every iteration till the gap size is greater than 0.