Sorting is the process of taking an unordered list of data and ordering it a specific manner. Numbers, names, and even objects can be sorted and the best algorithm to do the sorting depends on what is being sorted. The two most common forms of sorting are arranging a list of numbers in ascending or descending order and alphabetizing strings of characters. We sort records so that the individual data can be found more quickly. Could you imagine looking for your friends name in the New York phone directory if it was not placed in any order? The phone book if not alphabetized would be very inefficient to use when we need to know someone‘s phone number. When considering which sorting algorithm to use the following must be kept in mind: running time (the most important aspect), memory space, initial order, key range, and programming language. There are four sorting algorithms that are considered primitive they are selection sort, bubble sort, insertion sort, and enumeration sort. All of these have a worst case and average case Big O of O(n²). There are improvements to the basic sorting algorithms to improve their Big O the ones that are improvements of insertion sort are shellsort, treesort, and merge sort; these sorting algorithms have been improved to achieve the best possible search Big O which is O(n log n).

Insertion sort is one of the simpler sorting algorithms to program, understand, and teach. In its simplest form insertion sort takes an array of unsorted values and sorts them in a specific order. This is accomplished by dividing the list into two different sections the sorted section and the unsorted section. To start off all the values in the array are located in the unsorted section and no values are located in the sorted section. The first number from the array is taken and because it is the first and only number it is automatically located in the correct place in the sorted array. The second value is then read and placed in its proper position in the sorted list. Thus if the second value is greater than the first value it will be located to the right of the first value. (This is assuming we are sorting from least to greatest) The more minute aspects of this sorting algorithm can vary from program to program depending on preference of the individual. Note that as the sorted region grows by one each step the unsorted region gets smaller by one. For some of the insertions such as when 21 is placed into the sorted list the subsequent items must shift to make room. The worst case scenario for insertion sort is O(n²). Because of its simplicity and a Big-0 of O(n²) this sorting algorithm is best suited for smaller sized lists around 25 or so of in memory sorting. Insertion sort can be used with arrays and linked lists. This algorithm is especially important for sorting a list of numbers where the majority of values are in order but not all of them.

For an animated example of insertion sort please see: http://al.ei.tuat.ac.jp/~sekisita/isort-e.html

Shell sort an improved form of insertion sort it works by braking up the items to be sorted into smaller groups and sorting those smaller groups. Note below how the unordered numbers are broken up into 4 different groups and then the smallest value from that group is placed first into the slightly sorted list at the end of the first pass. For the second pass the numbers were broken up into only 2 groups and again the smallest value from group 1 is placed in the first position next the smallest value from group 2 is placed next and continue with the next smallest values and so on. To finish the sorting we do an insertion sort. This sort works best when using prime values for groups 1,2,3,5,7,11.…

Treesort is also an improved insertion sort. By using a tree to store the data as it comes in we can make the insertion sort more efficient and then use an inorder traversal to print out the ordered list from the tree. This is more efficient because new numbers can be added to the tree data structure more easily than placed into an array or linked list. The worst case for treesort is O(n²) but the average case being O(n log n).

Mergesort is a cousin of insertion sort it is based on the principle that there are 2 or more sorted lists and that the lowest value from any of the lists will be the lowest value of all the lists combined. This sorting algorithm can be written recursively also. The run time of this program with lists of size x and y is x + y and wit larger list sizes the run time increases linearly. For example given the smaller sorted lists of (1,6,9,16,25) and (8,11,12,45,55) the end result for a merge sort of these two lists would be (1,6,8,9,11,12,16,25,45,55) to get the smaller lists ordered you can use insertion sort or which ever sorting algorithm you wish.