Shell Sort and Quick Sort

Question 1

Define

Shellsort

Answer 1

Based on insertion sort.
1. Insertion sort woidely spaced items.
2. Insertion sort less widely spaced items, and so on
For example, do a sort on items four spaces apart, then 1 space apart.
O(N (logN)^2).

Question 2

Define

Interval/gap sequence

Answer 2

The sequence of numbers used to generte the intervals between the numbers sorted in shellsort. Popular method is Knuth’s interval sequence, h = 3 x h +1. Important that these numbers are relatively prime, more likely to intermingle items sorted on previous pass