8.3-2

8.3-2 Which of the following sorting algorithms are stable: insertion sort, merge sort, heapsort, and quicksort? Give a simple scheme that makes any sorting algorithm stable. How much additional time and space does your scheme entail?
insertion sort is stable because the comparison in the inner while will move elements to right only when they greater than key. if they are equal they dont move to right.

merge sort is stable the comparison in the merge compare L and R array only check if L is less than R . If it is equal it uses the element from L array which is in order with the input.

heap sort is not stable sort because the comparison is between left and right child and picks the greatest element. ex: 5 3 3 4. element 3 is not inserted in the correct order.

quick sort is not stable because we random procedure to get balanced split which can easily pick an similar element in the beginning and make it pivot element.

Give a simple scheme that makes any sorting algorithm stable.How much additional time and space does your scheme entail?

All we need to make sure is save the inserted order in another array and use it to break the tie for similar element values. we need to store indices from 1 to n each will need log n space(since an element has to written in the form 2^x and x will be no of bits ex: 8 needs 3 bits) we pick log n based on the maximum number. All the elements need $\theta(n log n)$ space.
Additional time: the worst case occurs when all elements are same and we need compare indices for every element. But the comparison occurs in constant time.