Describe the algorithm for removing a key from a hash table that resolves collisions using linear probing. You will loss points if leaving out details. You may give an example.

Consider an array of integers consisting of the number: 12 83 21 99 28 9 90 45 67 55 72. Use a gap value of k = 4.

1. How many interleaved lists are produced by the Shell sort?
2. Give the elements of each interleave list i.e. show each sub-list
3. Show the complete list again after sorting the interleaved lists.
4. Start with the list in step 3, pick a gap value of either 2 or 3. Show the interleaved lists.
5. What is the worst case time complexity of Shell sort if gaps are take to be (2^i) - 1, where i = 1, 2, ..k and 2^k = N array size?