There are four kinds of sorts.  There are sorts that search, sorts that swap,sorts that separate, and sorts that don't compare one element to another.  Inthe first class are the insertion sort, the extraction sort, and the heapsort. In the second class are the quick sort and the merge sort.  In thethird class are the bubble sort and the Shell sort.  In the last class arethe Radix-Exchange sort and the Pigeon sort.  (These lists aren't allinclusive. In fact, I know I'm leaving some sorts out, but I just want togive examples of what's in each class.)I won't talk about the last class because I don't find them particularlyinteresting.  Even though they are the fastest kind of sorts known, with O(N)sorts not only possible but practical in many cases, it is difficult togeneralize them, and I'm fond of finding general solutions to generalproblems.In the sorts that swap, the only variable is which elements are swapped.  TheShell sort starts by swapping elements that are far apart in hopes that any"large scale" disorder is eliminated quickly.  The bubble sort compares onlythose elements that are next to each other.  Each pair is compared and, ifthey are found to be out of order, they are swapped.The sorts that separate work by understanding that it is a lot faster to sortsmaller lists than bigger lists.  So, you seek to break up the lists intohalves and then break up the halves and then break up the quarters, and so onuntil each piece is small enough to sort.  (Often, a program will justcontinue to break the list down until each piece has a length of one.  A listof one item is already sorted.  On the other hand, many programmers prefer tostop after the element size gets small enough.)However, there is a choice to be made in this case.  Do you attempt to imposeorder on the list before or after you split it into parts.  The quick sort isa before sort.  The merge sort is an after sort.  When you quick sort a list,you choose a value, called the pivot, and you build your sublists such thatall of the elements which have a key value less than the pivot go into onesublist and those elements which do not go into the other.  Then, yourecursively sort each sublist and when that is done you simply append the"greater than" list to the "less than" list to make the whole sorted list.With a merge sort, you find the middle and break it there without any concernfor the key values of the elements, recursively sort each sublist and thenmerge the two sorted lists back together into one big list.  (The real nicething about the merge sort is you don't have to be able to pick a good pivotvalue in order for it to work well. Most of the algorithms for finding thebest pivot values start "Sort the list...")The insertion sort is what you do when you "build a sorted list."  Basically,you go through the unsorted list, and for each element, you find the place inthe sorted list where it should go and put it there.  This process isrepeated until there are no more elements in the unsorted list. Theextraction sort looks through the unsorted list for the element with thebiggest (or smallest) value and once it finds it, appends that element to thesorted list.  This process is repeated until there are no more elements inthe unsorted list.