quicksort algorithm stability

Question

Quicksort is not stable, since it exchanges nonadjacent elements.

Please help me understanding this statement.

I know how partitioning works, and what stability is. But I cant figure out what makes the above as the reason for this to be not stable? Then I believe the same can be said for merge sort - though it is quoted to be a stable algorithm.

Answer 1

Consider what happens during the partition for the following array of pairs, where the comparator uses the integer (only). The string is just there so that we have two elements that compare as if equal, but actually are distinguishable.

(4, "first"), (2, ""), (3, ""), (4, "second"), (1, "")

By definition a sort is stable if, after the sort, the two elements that compare as if equal (the two 4s) appear in the same order afterwards as they did before.

Suppose we choose 3 as the pivot. The two 4 elements will end up after it and the 1 and the 2 before it (there's a bit more to it than that, I've ignored moving the pivot since it's already in the correct position, but you say you understand partitioning).

Quicksorts in general don't give any particular guarantee where after the partition the two 4s will be, and I think most implementations would reverse them. For instance, if we use Hoare's classic partitioning algorithm, the array is partitioned as follows:

(1, ""), (2, ""), (3, ""), (4, "second"), (4, "first")

which violates the stability of sorting.

Since each partition isn't stable, the overall sort isn't likely to be.

As Steve314 points out in a comment, merge sort is stable provided that when merging, if you encounter equal elements you always output first the one that came from the "lower down" of the two halves that you're merging together. That is, each merge has to look like this, where the "left" is the side that comes from lower down in the original array.

while (left not empty and right not empty):
    if first_item_on_left <= first_item_on_right:
       move one item from left to output
    else:
       move one item from right to output
move everything from left to output
move everything from right to output

If the <= were < then the merge wouldn't be stable.