Previously we briefly mentioned bubble sorting as a possible solution, but noted that it was likely to not be efficient enough for larger n sized arrays. The bubble sort method iterates through an array and compares adjacent values and swaps them if they are out of place. This process happens throughout the entire array and usually requires us to keep track of two variables in a nested loop.
A visualization of Bubble Sorting:
Our minimum swap problem was solved with a variation of an insertion sort:
Visualization of Insertion Sort:
These methods both involve a O(n2) time complexity so we will explore more efficient ways of sorting using a mergesort strategy that combines the concepts of recursion, and divide and conquer.
Merge Sorting:
We break up our input array until there is only one element left (one element is by default sorted), then we merge the subArrays together until one sorted array remains.
This divide and conquer technique resolves the sorting by returning single element subArrays that are by default sorted. Thus when we pass left/right arrays to our merge function they are already sorted. Our mergeSort function then recursively is able to merge subArrays until only one final array remains, that has already been sorted. This allows for a logarithmic (dividing by 2 or halving) run time.