Wednesday, 17 October 2012

Merge Sort

If you have an array of 8 elements, merge sort works by grouping these 8 into 4 sorted sets of 2. The sort is done through sibling pairs.

With these 4 pairs, you pair these with their siblings and take the first elements of each. Compare element 1 in both and place the lowest value in a third new array. You then compare element 1 with element 2 and place the lowest in the third array. This will go on until you are left with single pair merge sorting into a single final array.

Insertion Sort

Insertion sort works by maintaining a fully sorted list and inserting unsorted data one at a time then immediately sorting it.

So to begin with you have a single element, and that is considered sorted.
Then you add an item to the right of it. You compare these with each other and you might have to swap them. Then you have a sorted list of 2.
Then you add another item to the right of your list. You compare this with the one before it, if they're already sorted then you're done comparing for that iteration, otherwise swap them and move to the left. This goes on till you have no more data to insert.

Bubble Sort

Bubble sort is a simple sorting algorithm that compares the first two elements in the array and keeps hold of the largest, for each pass the largest will 'bubble' to the top. Each pass will require n-i comparisons.

This algorithm is considered O(N^2)