Shell Sort

• A modified Insertion Sort
• Instead of sorting the entire array, sort many smaller subarrays using insertion sort before sorting the entire array
• Compares all elements that are a gap apart, and swap those elements if needed
  • Keep reducing the gap (halfing it in our case) until it is 0

Implementation

• Uses a gap function
  • Often $n/2.2$
  • We will use $n/2$ to make it easier to think about

Set the initial value of gap to n / 2
while gap > 0
	for each element from position gap to the last element
		Insert element where it belongs in its subarray
	if gap is 2
		set it to 1  
	else
		gap = gap / 2 // chosen by experimentation

Time Complexity

• A general analysis is still an open problem
• Performance depends on the gap function chose
  • Successive powers of 2 → $O(n^2)$
  • Hibbard’s Sequence $2^k-1$ → $O(n^{3/2})$