In Lecture 6, we sketched the radio sort algorithm for sorting an array of n ddigit integers, with each digit in base is, in linear time @(d(n +...

Would love to know how to go about thinking question 18. Would appreciate a hint for question 19. Thanks!

In Lecture 6, we sketched the radio sort algorithm for sorting an array of n d—digit integers, with each digitin base is, in linear time @(d(n + 16)). The basic algorithm is as follows: for j=1..d dosort the input stably by each element’s jth least-significant digit The sort we used in each pass through the loop was Counting Sort, but any stable sort will work (albeitperhaps with different overall complexity). We tried this algorithm and saw that it worked on an example. Your job is to prove inductively that thisalgorithm works in general. The class notes suggest proving the following loop invariant: after 3' passesthrough the loop, the input is sorted according to the integers formed by each element’s j least-significantdigits. 18. State and prove a suitable base case for the proof. 19. Now state and prove an inductive case for the proof. You may assume that the per-digit sort used ineach iteration is (1) correct and (2) stable.