Sorting

Sorting a list can be a very easy task, or one that is very daunting.
A method that i found called quicksort, seems to be very efficient, and interesting to think about.

1. Pick an element, called a pivot, from the list.
2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

-Taken from Wikipedia.org - Quicksort


So let's take the list:
3 7 8 5 2 1 9 5 4
For a pivot, let us take 5, because we know that that number is halfway between 1 and 9.

In the picture, the red numbers represent all numbers greater than 5, and the blue represent all numbers less than or equal to 5.
5 is first taken out of the list. Then the elements are sorted into the two groups, blue numbers, and red numbers. Next 5 is put back into the list. Now, the blue elements, numbers less than 5, and the red elements, numbers greater than 5, can now be sorted by using this process recursively.

So the first group goes like this:
3 4 2 1 5
5 4 2 1 3
2 4 5 1 3
2 1 5 4 3
2 1 3 4 5
Then the process will occur again, sorting the 1 and 2.