Intermediate Sorting Algorithms: Merge, Quick and Radix Sort

In my last article, I walked through more intuitive but less efficient sorting algorithms: bubble, selection and insertion sort. If you’re just starting out, read that first: https://medium.com/@verdi/the-quadratic-sorting-algorithms-an-overview-of-bubble-selection-and-insertion-sort-266de2b26004

In this article, I’ll cover merge, quick and radix sort — giving an overview of each followed by pseudocode (if you want to try and implement), the implementation code and a quick blurb on its Big O complexity.

Merge Sort

Overview

Merge sort works by taking advantage of the fact that arrays of zero or one element are already sorted. So, given an array, you decompose the array into smaller sub arrays until you are dealing with arrays of zero or one element. Then you recompose the arrays and with each merging you determine the correct order of the subarrays. Eventually, you work your way up the stack merging the final two arrays and returning the sorted array.

Here’s an overview with an array containing the numbers 1–8. You divide each array at its midpoint until you reach single element arrays. Then you merge each one together, sorting the order with each merger.

overview of merge sort

Pseudocode

1. Write a helper method called merge which takes two arrays and returns a single sorted array. Do not mutate either of the original arrays.
2. Split the original array in half. You should create a pointer for the left side and right side respectively. Then, recursively keep splitting each side in half until you reach a single element array on each side. That is your break case.
3. Now, recompose each array, calling the merge function on each of the two sub arrays.
4. Return the sorted array.

Implementation Code

Merge function

function merge(arr1, arr2){
    let i = 0
    let j = 0
    let arr = []
    while (arr.length < (arr1.length+arr2.length) ) {        
        if (i===arr1.length){
            arr = arr.concat(arr2.slice(j))
        } else if (j===arr2.length){
          arr = arr.concat(arr1.slice(i))
        }
    if (arr1[i] < arr2[j]) {
            arr.push(arr1[i])
            i++
        } else if (arr1[i] > arr2[j]) {
            arr.push(arr2[j])
            j++
        } else if (arr1[i] === arr2[j]) {
            arr.push(arr1[i])
            arr.push(arr2[j])
            i++
            j++
        }
    }
    return arr
}

Merge Sort

function mergeSort(arr){
  if (arr.length <= 1) {
    return arr
  } else {
    let half = Math.floor(arr.length/2)
    let first = arr.slice(0,half)
    let second = arr.slice(half,arr.length)
    return merge(mergeSort(first), mergeSort(second))
  }
}

Big O Complexity of Merge Sort

Big O for Merge sort is O(n log n). What the heck is n log n? Well, recall logarithms are the opposite of exponents. With each pass through the array, we are splitting it in half. So, if you had 32 elements in the array, it’d take 5 passes to get to single element subarrays (2–4–8–16–32) — that’s the log n bit. Now, the first n refers to the fact that you have to scan through each subarray. The bigger the subarrays, the longer the algorithm takes.

Big O Complexity for Merge Sort

Quick Sort

Overview

Quick sort works by finding a pivot point within the array. The pivot point can be chosen randomly or you can just pick the first element in the array. Then, working left to right, all the numbers which are greater than the pivot point are placed on the right hand side and all the numbers less than the pivot point are placed on the left hand side. In doing this, you now have the correct index for the pivot point.

You repeat this process, working smaller unsorted subarrays until you have sorted the entire array. To be clear, you never make actual subarrays, instead you create two pointers, a beginning and end which work on the same array.

The image below shows a first pass through an array of elements 1–8. The pivot point is picked randomly (5). All elements less than 5 are moved to left of it and all elements greater are moved to the right.

demoing a pivot point for quick sort

Pseudocode

1. Start by creating a pivot helper method. This method should take three arguments: an array, a starting index and an ending index.
2. It should mutate the original array by moving all the elements that are less than the pivot to the left and all values that are greater to the right. It needs to do this in place as well, without creating other arrays. Finally, it should return the proper index of the pivot point.
3. With the pivot method created, recursively repeat this process. Each time through, you’ll pass the original array, but the start and end indexes should be updated based on the return value of the pivot method. The break case is when the left and right points converge (remember, single element arrays are already sorted!).
4. Return the sorted array.

Implementation Code

Pivot helper method

function pivotPoint(arr, startIdx=0, endIdx=arr.length-1){
    function swap(arr, idx1, idx2){
        let temp = arr[idx1]
        arr[idx1] = arr[idx2]
        arr[idx2] = temp
    }  
   
    let pivotIdx = startIdx
    let pivotVal = arr[startIdx]
    for (let i=startIdx+1;i<=endIdx;i++){
        if (pivotVal > arr[i]) {
            pivotIdx++
            //swap higher and lower values
            swap(arr, i, pivotIdx)
            
        }
    }
    //swap final values
    swap(arr, startIdx, pivotIdx)
    return pivotIdx
    
}

Quick Sort

function quickSort(arr, left=0, right=arr.length-1){
    if (left < right){ //pointers will converge on each side
        pivotIdx = pivotPoint(arr, left, right)
        quickSort(arr, left, pivotIdx-1) //left side
        quickSort(arr, pivotIdx+1, right) //right side
    }
    return arr
}

Big O Complexity for Quick Sort

On average, the Big O complexity for Quick sort is the same as Merge sort — O(n log n). Again, this is because with each pass in the array you are chunking the data in half. However, notice the worst case time complexity below — O(n²). This happens when you choose the first element in the array to be your pivot point and you are dealing with a sorted or nearly sorted array. In a sorted array, each pass through you move no values to the left hand side, which means each pass you have to iterate through the entire array.

You can overcome this shortcoming by not automatically selecting either the beginning or end value in the array to be the pivot point — instead choose a random index.

Big O Complexity for Quick Sort

Radix Sort

Overview

Radix sort is different from Merge and Quick sort in that it is not a comparison sort. Instead, Radix sort takes advantage of the bases of each number to group them by their size. As a result, Radix sort can only be used with numeric based data — not strings.

The easiest way to explain Radix sort is through an example. If we wanted to sort the numbers in the array: [333,1,12,9,987,9877] we’d create 10 buckets where each bucket represents 0–9. We are using 0–9 because our number system is base 10. If we were sorting binary numbers, we’d only have 2 bucks, 0–1.

Now, we start by looking at the last value in each number and then drop it into the corresponding bucket. So, for the number 9877 we’d look at the value 7 and then place it into our 7’s bucket. Once all the numbers are in their right bucket, we merge the buckets into a single array and repeat the process until we’ve covered the max digits in our data set, in this case 4 because 9877 has 4 digits. Remember, 0 is a valid placeholder, so 0007 is the same as 7.

The first image shows an array of numbers with 10 buckets set up. The second image shows a first pass, where the numbers are grouped by the value contained in their one’s position. The third image shows the numbers being merged into a single array again, in the order they existed in the buckets.

radix sort — initial bucket creation

radix sort — first grouping

radix sort — merge buckets into single array

Pseudocode

1. Create a helper method called getDigit(num, place) which takes a number a returns the digit located at the passed in place (one’s, ten’s, hundred’s position etc.).
2. Create another helper method called digitCount(num) which returns the total digits of a number. So, digitCount(123) // returns 3
3. Create a top level loop which iterates as many times as there are digits in the biggest number. So if 1234 is the biggest number in the set, then the loop should go for four times.
4. Within the top loop, create two sub array buckets. One for positive numbers and one for negative numbers.
5. Loop through every value in the array. First check to see if the number is greater than or equal to 0. This is how you know whether to place the number in the positive or negative buckets. Next, use the getDigit() function to determine the proper bucket and add it.
6. Set the new value of the array to be the concatenated values of the negative and positive arrays.
7. Return the sorted array.

Implementation Code

getDigit and digitCount helper methods

function getDigit(num, place){
    strNum = String(num);
    if (strNum.length-1 < place) return 0
    let idx = (strNum.length-1) - place
    return strNum[idx] === "-" ? 0 : Number(strNum[idx])
}
function digitCount(num){
    return String(Math.abs(num)).length
}

Radix sort

function radixSort(arr){
    let maxDigits = digitCount(Math.max(...arr))
    for (let i=0;i<=maxDigits;i++){
        let posBuckets = Array.from({length: 10}, () => [])
        let negBuckets = Array.from({length: 10}, () => [])
        
        arr.forEach((num) => {
            let digit = getDigit(num, i)
            if (num >=0){
                posBuckets[digit].push(num)
            } else {
                negBuckets[digit].push(num)
            }
        })
        arr = [].concat(...negBuckets, ...posBuckets)
    }
    return arr
}

Big O Complexity for Radix Sort

Generally speaking, the Big O complexity for Radix sort should be better than Merge and Quick sort. The biggest factors are n which is the total size of the initial array and k which is how many iterations need to be made which is based of how many digits the biggest number contains.

Big O Complexity for Radix Sort