Welcome To Sora Park

Shell Sort is an in-place comparison sort that can be seen as either a generalisation of sorting by exchanging or sorting by insertion.

Insertion Sort is slow since it compares and exchanges only elements in neighbour, and Shell Sort solves this problem by allowing comparison and exchange of elements that are far apart to gain speed!

# Basic Idea

To arrange the list of elements so that, starting anywhere, taking every hth element produces a sorted list, which is called h-sort.

# Pseudocode

arr: array of elements
n: length of array
gap

tmp: temp value
j: temp index

for gap = n / 2; gap > 0; gap /= 2 do:
	for i is gap to n - 1 do:
    	/* select value to be inserted */
    	tmp := arr[i]
        
        /* shift element towards right */
        for j = i; j >= gap and arr[j - gap] > tmp; j -= gap do:
        	arr[j] := arr[j - gap];
        end for
        
        /* insert the value at hole position */
        arr[j] := tmp;
        
	end for
end for

# Computation in C

# Time Complexity

• Worst-case:
  - O(n^2) (worst known worst-case gap sequence)
  - O(n log^2 n) (best known worst-case gap sequence)
• Best-case performance:
  - O(n log n) (most gap sequences)
  - O(n log^2 n) (best known worst-case gap sequence)
• Average performance depends on gap sequence
• Worst-case space complexity:
  - О(n) total, O(1) auxiliary

The running time of this algorithm is heavily dependent on the gap sequence it uses!