calgorithmsortingshellsort

h-sorting in Shell sort

In shell sort, 3h+1 sequence is recommended to h-sort a list using insertion sort

//1, 4, 13, 40, ...

Optimal formula to compute start value of h is one-third of listsize, as shown below,

int h = 1;
while(h < listSize/3){ // why N/3?

  h = 3*h + 1
}
while(h >= 1){

  //h-sort the array
  // perform insertionSort
  h = h/3;
}

Question:

To perform shell sort, How to prove mathematically that h(at max) should be less than listSize/3?

Solution

  • If we continue to increase h after condition (h < listSize/3), h becomes larger than listSize, and there is no sense in h-sorting - we cannot compare items A[i] and A[i+h] because the second index is beyond list range.