*If k=1, then a valid ordering would be 1, 2, 3, 4, 5, 6, 7, 8, 9.

*If k=2, then a valid ordering would be 1, 2, 4, 3, 7, 6, 8, 9.

2. Sorting (5+6+5-16) (a) Consider a sequence of numbers where items at distance k are sorted. For example if k 1, then a valid ordering would be 1,2, 3,5,4, 6,7,8,9. If k 2, then a valid ordering would be 1,3,4, 2,7,6,8, 9. Based on this information answer the following questions; i. Design an algorithm to sort the complete list, i.e., the order should be 1,2,3, 4,5,6, 7,8,9, given that items at distance k are sorted. Clearly write the steps of your algorithm and illustrate the steps with an exam- ple(5) ii. Show how your example works on the following sequence 1,3, 4,2,7,6,5, 9, 8 ii Compute the complexity of your algorithm. Explain your steps clearly