What is the best case input for Shellsort?

A sorted array because each sublist is sorted in linear time
  • A reverse sorted array because because all the sublists are sorted in linear time
  • A random array, without too much order or dis-order, which will keep things balanced
  • It doesn't matter, all inputs of a given size will cost the same

The order of the input does affect the cost.

Remember what sort is used for sorting the sublists.

Insertion sort is used to sort the sublists.

Insertion sort's best case is when the input is ordered

If the input to Shellsort is ordered, than the input to each call to Insertion sort on the sublists will also be ordered.