Sorting Algorithms: Merge Sort and Quick Sort(Part 2)
In relation to time complexity Merge Sort and Quick Sort provide a more efficient way of sorting. Below is a breakdown of how they work, and how they are implemented using JavaScript.
Merge Sort: divides given (unsorted array) into halves until each element is in its own separate array. Separate arrays are then merged back in order based on comparison of the elements.
- Space complexity: O(n) (not good)
- Time Complexity: O(log n) good
We can see the array [15,3,2,9,6,7,8,6] being separated with the black arrows, and then merged back together (in order) with the green arrows.
MergeSort Function: (denoted with black arrows, and white numbers) To implement mergeSort we use recursion. In addition to the helper function merge() to compare and combine arrays.
When calling the mergeSort() function with arr=[15,3,2,9,6,7,8,6] the first thing we will do is find the mid point (let mid = Math.floor(arr.length/2))denoted by the 1. We then use this mid point to break the array in half (left = arr.slice(0,mid) & right = arr.slice(mid)).
Next we call mergeSort on the left side (15,3,2,9) denoted by the 2. Since we are calling it recursively, and have yet to hit our base case, it will be again called on the left side (15,3). Finally mergeSort is called on the left (15) and meets the base case (if(arr.length ≤1)return arr) returning 15. Next we call mergeSort on the right side and return 3. Now that we have a left, and right argument we can call merge([15],[3]) and look at this function in detail.
Merge Function: (denoted with green arrows, and pink numbers)the first while loop (while(i < arrOne.length && j < arrTwo.length)) applies when we are looping through the two arrays both at the same time. As we do have two arrays we can now check our condition. The condition compares the value of the indices of the two arrays (if(arrTwo[j]>arrOne[i])…). In this case arrOne[0]=15 and arrTwo[0]=3. The smaller value (3) is then add to the sorted array (sorted.push(arrTwo[j])), and the index moves forward one (j++).
However we have now exhausted our while loop condition, as we only have one item in the array and j is now equal to arrTwo.length. Therefore we hit our second while loop (i<arrOne.length), and .push() everything in arrOne to our sorted array (sorted.push(arrOne[i]) i++), and exiting the while loop as is now equal to arrOne.length. We then return the sorted array of [3,15]. This same process is followed moving forward next with the arguments merge([2],[9])…merge([3,15],[2,9])…merge([5],[7])… and so on, until we get the fully sorted array. (steps shown in the image)
Quick Sort: First you pick a random “pivot” for your list, and two pointers (left & right). We move the left pointer until we reach an element that should be swapped (>7), and do the inverse on the right. Once this is completed, the list is broken down into two lists, and the same procedure is performed on each. This is done until the list is sorted.
- Left: 15 is greater than 7, so we hold that point until we can swap it with a value on the right
- Right: 6 is less than 7, so we swap it with 15
- Left: 3 is less than 7, so we move on to 2
- Right: 8 is greater than 7, so we move on to 5
- Left: 2 is less than 7, so we move on to 9
- Right: 5 is less than 7, so we hold that point until we can swap it with a value on the left
- Left: 9 is greater than 7, so we swap it with 5
- Pivot1,Left: 6 is greater than 3, so we hold it until we can swap
- Pivot1,Right: 5 is greater than 3, so we move on to 2
- Pivot1,Right: 2 is less than 3, so we swap it with 6
- Pivot2,Left: 9 is greater than 8, so we hold it until we can swap
- Pivot2,Right: 15 is greater than 8, so we move on to 7
- Pivot2,Right: 7 is less than 8, so we swap it with 9
We will continue to breakdown the list, as follows, until it is ordered.
