Question 6 - 20 points The quick sort algorithm discussed in the lecture is not a stable sort algo- rithm because the partition operation does not preserve the order of elements

with same key value. Design an improved linear time partition operation that does preserve the order so it can enable stable quick sort. You may use extra memory in your design. Explain why it runs in linear time.