Sorting Algorithms

Insertion Sort

Start at index one. Store the value in a variable. Compare it to the values to the left. If a value to the left is larger, it gets shifted to the right. If the value is not larger, then we place the value in the empty spot. O(n²)

Selection Sort

Start at index zero. Mark value as the minimum. Go through the array and change the value of the minimum if you find something smaller. Once you went through the array, swap the value of the minimum with the value you started with. Decrease the size of the array. O(n²)

Bubble Sort

Start at index zero. Compare its value to the one next to it. If the starting value is bigger, we swap. We end once we complete a pass where no swaps were done. O(n²)

Quick Sort

Mark a point in the array as a pivot. Mark J at the beginning of the array. Mark I at it the index before J. If the value at J is less than the value at the pivot, we increment I - then we swap the values of I and J.  Increment J regardless.  Once J reaches the pivot,  we increment I and swap the pivot with I.  

We know the pivot is in the correct place if the values to the left of it are smaller and the values to the right of it are bigger.  Quick Sort will begin again but this time the two partitions. Quick Sort is recursive and will continue until each partition is complete. O(n logn)

Merge Sort

We divide the array in two. We continue to divide each array into two smaller pieces until every array has a size of one. We then merge these arrays back together while making sure they are in order one step at a time. O(n logn)