Which of these inputs will cost the most for Shellsort when using divide-by-twos increments on an array with a size where n is a power of 2?

An array where even positions store values 1 to n/2 and odd positions store values n/2+1 to n
  • A sorted array
  • A reverse sorted array
  • An array with random input

A sorted array will result in every sublist also being sorted, which is fast.

An array with random input is unlikely to give the worst case.

A reverse-sorted array turns out not to cause any particular problem.

When the array size is a power of 2, the divide-by-twos increment series will keep the even-position items separate from the odd-position items until the final pass, resulting an a really expensive final pass.