The definition of a stable sorting algorithm is given on page 196. Is quicksort stable?

Finally, the for loop of lines 1012 places each element A[j] into its correct sorted position in the output array B. If all n elements are distinct, then when we first enter line 10, for each A[j], the value C[A[j]] is the correct final position of A[j] in the output array, since there are C[A[j]] elements less than or equal to A[j]. Because the elements might not be distinct, we decrement C[A[j]] each time we place a value A[j] into the B array. Decrementing C[A[j]] causes the next input element with a value equal to A[j], if one exists, to go to the position immediately before A[j] in the output array. How much time does counting sort require? The for loop of lines 23 takes time (k), the for loop of lines 45 takes time (n), the for loop of lines 78 takes time (k), and the for loop of lines 1012 takes time (n). Thus, the overall time is (k + n). In practice, we usually use counting sort when we have k = O(n), in which case the running time is O(n). Counting sort beats the lower bound of S2(n Ign) proved in Section 8.1 because it is not a comparison sort. In fact, no comparisons between input elements occur anywhere in the code. Instead, counting sort uses the actual values of the elements to index into an array. The S2(n lg n) lower bound for sorting does not apply when we depart from the comparison sort model. An important property of counting sort is that it is stable: numbers with the same value appear in the output array in the same order as they do in the input array. That is, it breaks ties between two numbers by the rule that whichever number appears first in the input array appears first in the output array. Normally, the property of stability is important only when satellite data are carried around with the element being sorted. Counting sort's stability is important for another reason: counting sort is often used as a subroutine in radix sort. As we shall see in the next section, in order for radix sort to work correctly, counting sort must be stable