## Changing the order of a sorted list by sorting it.

One of the obscure problems that was discovered early on by certain Quick Sort implementations, is that sorting an
already sorted list can change the order of the list.

This is sometimes called "stable" (as in, Quick Sort is not a stable sort).

Two values can be equal according to the invariant, even though they aren't equal in the parts that aren't compared.

Usually this problem can be avoided by paying attention to the original order of equal elements.

This is one reason why Quick Sort usually picks a pivot from (or at least considering) the middle of the list.

Another similar problem is when different implementations use random or poorly defined methods to pick arbitrary values.

Two different methods for selecting the pivot in Quick Sort could cause equal elements to end up in different places in the sorted list.

This usually doesn't matter, but can cause headaches when a new and improved algorithm doesn't produce exactly the same results as the old and inferior one.

These problems have led to an attempt to define the behavior that "should" happen when equal values are sorted.

In My Opinion, if an "equal" value came before another "equal" value in the unsorted list, it should come before it in the sorted list, but opinions differ.

If you're rolling your own sorting function, this problem probably doesn't matter to you.

But if you're building a library function you should probably specify exactly how it handles the equal-values case.