Which of the following sorting algorithms are stable: insertion sort, merge sort, heap sort, and quick sort? Give a simple scheme that makes any sorting algorithm stable. How much additional time and space does your scheme entail?
Answer to relevant QuestionsUse induction to prove that radix sort works. Where does your proof need the assumption that the intermediate sort is stable?Show how quick sort can be made to run in O (n lg n) time in the worst case.Consider a version of the division method in which h (k) = k mod m, where m = 2p – 1 and k is a character string interpreted in radix 2p. Show that if string x can be derived from string y by permuting its characters, then ...Show that the longest simple path from a node x in a red-black tree to a descendant leaf has length at most twice that of the shortest simple path from node x to a descendant leaf.Can the black-heights of nodes in a red-black tree be maintained as fields in the nodes of the tree without affecting the asymptotic performance of any of the red-black tree operations? Show how, or argue why not.
Post your question