
Slow sorting algorithms
 O(n), O(n^{2})...
 Selection Sort
 Bubble sort,
 Insertion sort
 All are O(n^{2})

Searching algorithms
 Linear Search, O(n)
 Binary Search, O(log[n])

Binary search algorithm sketch
 Find the mid point between the bounds
 Compare the midpoint with the key (<, ==, >)
 Adjust the bounds (if needed)
 Iterate (if needed)

Why is binary search fast?
 The search area is reduced by half each time
 log(n)

Selection sort sketch
 Start at the first index
 Scan the array for any values smaller than index
 Swap when appropriate
 Iterate the index and repeat

Fast sorting algorithms
 Quicksort
 Merge Sort
 Heap Sort

Merge Sort Sketch
 Recursively split the array in to halves and subhalves
 Create a temporary array of equal size
 Combine the halves by placing the smaller elements into the temp array first
 Copy any remaining elements
 Copy everything back into the initial array
 Recursive process

