QuickSort (C.A.R. Hoare).

The idea is this:  And there are many variations on this theme:

Pick one element in the array to be the pivot.  (I choose a random one.  Some people pick the last element.  Some people pick the first element.)

Then you split the array into two pieces:  the stuff that comes before the pivot, and the stuff that comes after the pivot.  And then you put the pivot in its correct location.  If you know what you are doing, you can do this WITHOUT a second array.

Then you recursively sort the low half and the high half.



                    v
    Q E R P I O T W Y U
              ^

QuickSort

Pros:  very fast (fastest of the relatively simple sorts to code)
Does not use extra storage space other than a few local variables (it does not need another array)

Cons:  Does use recursion.  (Harder to code in older languages).
Uses randomness, which is iffy, especially in languages without a random number generator.
If you choose a bad pivot EVERY TIME, this sort runs SLOOOOOOW.  (Odds of this actually happening are lower than the odds of a supernova.)

If you're not careful, your QuickSort will run SLOOOOW if there are a lot of ties (a lot of equal elements in the array).

Not stable.  If we could only make this stable, this would also solve the "ties" problem.

Making a sort stable.  No matter what sort you're using:  good, bad, whatever, there is value in making it stable.  This means that ties, elements with the same value are handled properly.  They end up in the sorted array in the same relative order as the original array.

Some sorts are just naturally stable:  the MergeSort just works.

Most sorts are not:  ShellSort, TreeSort, QuickSort, HeapSort.

To make any sort stable:

append a tag field to your sorted information.

So instead of sorting

Q W E R T U I O P

Sort this:

Q W E R T Y U I O P
0 1 2 3 4 5 6 7 8 9

Whenever you do a comparison, if one element comes before another, GREAT, just do what you would normally do.  If there is a tie, then look at the tag fields, and the one with the lower tag field is the one that comes first.

A A B M N T
1 4 0 3 5 2

(You can make a class with String value; int tag or something like that.)