Bubble Sort

1. Iterate over the list, compare each element with the next element, and if the next element is smaller swap the two.
2. For each swap completed increment a counter.
3. If at the end of the list the swap counter is greater than 0, reset it to zero and start again at step 1.
4. If the swap counter == 0, then the array is in sorted order.

Array to be sorted: [7 4 6 5 3] Pass 1: [4 6 5 3 7] Pass 2: [4 5 3 6 7] Pass 3: [4 3 5 6 7] Pass 4: [3 4 5 6 7]

Insertion Sort

The Insertion Sort algorithm is the method that many people use to sort playing cards. Pick up one card at a time and insert it so that the cards stay sorted.

Array to be sorted: [7 4 6 5 3] Pass 1: [4 7 6 5 3] Pass 2: [4 6 7 5 3] Pass 3: [4 5 6 7 3] Pass 4: [3 4 5 6 7]

Merge Sort

Merge sort is a more efficient sorting algorithm than Selection Sort, Bubble Sort and Insertion Sort, with a time complexity of O(n log n). It has a relatively high space complexity of O(n) compared to some other algorithms that we won't cover in this class. The Java libraries implement MergeSort, but only in specific cases.

mergeSort(arrayToSort[], leftIndex, rightIndex)

If rightIndex > leftIndex:

1. Find the middle point to divide the array into two halves: int middleIndex = (leftIndex + rightIndex) / 2
2. Call mergeSort for first half: mergeSort(arrayToSort, leftIndex, middleIndex)
3. Call mergeSort for second half: mergeSort(arrayToSort, middleIndex + 1, rightIndex)
4. Merge the two halves sorted in step 2 and 3: merge(arrayToSort, leftIndex, middleIndex, rightIndex)