An Intro to Advanced Sorting Algorithms: Merge, Quick & Radix Sort in JavaScript

In a previous article, we looked at some elementary sorting algorithms like bubble sort, selection sort and insertion sort. While these algorithms are easy to understand and implement, they don‘t scale well for large datasets due to their quadratic time complexity.

In this article, we‘ll dive into some more advanced sorting techniques – namely Merge sort, Quicksort and Radix sort. These algorithms are much more efficient with an average time complexity of O(n log n). Let‘s jump right in!

Merge Sort

Merge sort is a classic "divide and conquer" algorithm. The basic idea is to split the unsorted list into n sublists, each containing one element (a list of one element is considered sorted). Then repeatedly merge the sublists to produce new sorted sublists until there is only one sublist remaining.

Here‘s a step-by-step breakdown of the process:

1. Divide the unsorted list into n sublists, each containing 1 element.
2. Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

Let‘s visualize this with an example. Consider the array: [8, 3, 5, 4, 7, 6, 1, 2]

First, we divide the list into sublists of size 1. Then, we merge adjacent sublists to create sorted sublists of size 2, then 4, and so on until the entire list is merged back together.

The key operation in merge sort is the merging of two sorted lists. This is where most of the comparisons and swaps happen. To merge two sorted sublists, we compare the first element of each sublist and copy over the smaller element into a new list. We keep doing this until both the original sublists are empty.

Here‘s what the code for merge sort might look like in JavaScript:

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let result = [];
  let i = 0;
  let j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }

  return result.concat(left.slice(i)).concat(right.slice(j));
}

The mergeSort function recursively splits the array in half until it has sublists of length 1 which are by definition sorted. The merge function then merges these sorted sublists back together.

Time Complexity Analysis

To analyze the time complexity of merge sort, let‘s break it down into the recursive splitting phase and the merging phase.

In the splitting phase, we recursively divide the list in half until we reach sublists of size 1. Since we split the list in half at each level of recursion, there will be log n levels, where n is the size of the original input.

Level 0: n
Level 1: n/2, n/2  
Level 2: n/4, n/4, n/4, n/4
...
Level log n: 1, 1, 1, 1, 1, ..., 1 (n elements)

At each level, we do a constant amount of work to split the lists. So the total time for splitting is:
1 + 2 + 4 + 8 + … + n/4 + n/2 + n = 2n – 1 ~ O(n)

In the merging phase, at each level we do a total amount of work that is proportional to the number of elements. So the total time for merging across all levels is:
n + n + n + … + n = n log n ~ O(n log n)

Therefore, the overall time complexity of merge sort is O(n log n). This is a big improvement over the quadratic time sorts we saw earlier!

Quicksort

Quicksort is another widely used efficient sorting algorithm that follows the divide and conquer paradigm, similar to merge sort. However, unlike merge sort which does the bulk of its work in the merging phase, quicksort does more work in the partitioning or splitting phase.

Here‘s how it works at a high level:

1. Select a ‘pivot‘ element from the array. This could be any element, but a common choice is the last element.

2. Reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it. This partitioning step can be done in-place without using additional arrays.

3. Recursively apply steps 1 and 2 to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

Let‘s visualize this with the same example array: [8, 3, 5, 4, 7, 6, 1, 2]

We choose 2 as the pivot. After the partitioning step, the array looks like this:
[1, 2, 5, 4, 7, 6, 8, 3]

Then we recursively sort the subarrays [1] and [5, 4, 7, 6, 8, 3].

Here‘s a possible JavaScript implementation:

function quickSort(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    const pivotIndex = partition(arr, left, right);
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
  }
  return arr;
}

function partition(arr, left, right) {
  const pivot = arr[right];
  let i = left - 1;

  for (let j = left; j <= right - 1; j++) {
    if (arr[j] < pivot) {
      i++;
      swap(arr, i, j);
    }
  }
  swap(arr, i + 1, right);
  return i + 1;
}

function swap(arr, i, j) {
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

The quickSort function recursively partitions the array using the partition function until the subarrays have length 1. The partition function selects the last element as the pivot, iterates through the array, swapping elements less than the pivot to the start of the array.

Time Complexity Analysis

In the best case, the partitioning step always picks the median as the pivot. This means we partition the list into two nearly equal-sized sublists. Similar to the analysis for merge sort, there will be log n levels of recursion, and at each level, we do a total amount of work that is proportional to n. So the total time is again O(n log n).

However, in the worst case, the partitioning step picks the smallest or largest element as the pivot. This means one of the partitions will contain just one element and the other partition will contain n – 1 elements. In this case, quicksort degenerates to O(n²).

On average though, the partitioning step picks an element that is not too far from the median, and the split is not too lopsided. Therefore, the average running time is still O(n log n).

Radix Sort

Radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value. It works by sorting the elements based on their radix or base (e.g., base 10 for decimal numbers).

Here‘s how it works:

1. Find the maximum number to know the number of digits.
2. Do counting sort for every digit, starting from the least significant digit to the most significant digit.

Consider the array: [170, 45, 75, 90, 802, 24, 2, 66]

We start by sorting by the ones place. Then we sort by the tens place, and finally the hundreds place.

Here‘s a JavaScript implementation:

function radixSort(arr) {
  const maxNum = Math.max(...arr);
  let digit = 1;
  while (maxNum / digit > 0) {
    countingSort(arr, digit);
    digit *= 10;
  }
  return arr;
}

function countingSort(arr, digit) {
  const counts = new Array(10).fill(0);
  const output = new Array(arr.length).fill(0);

  for (let i = 0; i < arr.length; i++) {
    const place = Math.floor(arr[i] / digit) % 10;
    counts[place]++;
  }

  for (let i = 1; i < 10; i++) {
    counts[i] += counts[i - 1];
  }

  for (let i = arr.length - 1; i >= 0; i--) {
    const place = Math.floor(arr[i] / digit) % 10;
    output[counts[place] - 1] = arr[i];
    counts[place]--;
  }

  for (let i = 0; i < arr.length; i++) {
    arr[i] = output[i];
  }
}

The radixSort function first finds the maximum number to determine the number of digits. Then it does a counting sort for each digit, starting from the least significant digit to the most significant digit.

Time Complexity Analysis

Let‘s denote the number of elements in the input array as n, and the number of bits required to store the largest number as k. In each iteration, we perform a counting sort on n elements, which takes O(n+b) time, where b is the base (10 for decimal). We do this for each of the k digits. Therefore, the total time complexity is O(k(n+b)).

In the worst case, the largest number has k = log_b(max) digits. So the worst-case time complexity is O((n+b) * log_b(max)).

If k is constant (i.e., the number of digits is bounded), then radix sort runs in linear time — O(n).

Comparison and Use Cases

So how do these advanced sorting algorithms compare? Here‘s a quick summary:

Algorithm	Best Case	Average Case	Worst Case	Space Complexity
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)
Quicksort	O(n log n)	O(n log n)	O(n²)	O(log n)
Radix Sort	O(n+b)	O((n+b) * log_b(max))	O((n+b) * log_b(max))	O(n+b)

Merge sort has a guaranteed time complexity of O(n log n), but it requires O(n) additional space. Quicksort is usually faster in practice and requires only O(log n) additional space on average, but has a worst-case time complexity of O(n²). Radix sort can sort in linear time if the number of digits is constant, but it‘s only applicable for integer sorting.

In practice, the choice of sorting algorithm depends on the specific characteristics of the data and the constraints of the problem. If you have a small dataset, the simpler quadratic sorts might suffice. If you need a stable sort (preserves the relative order of equal elements), merge sort is preferred. If you‘re sorting integers within a fixed range, radix sort is ideal. For general-purpose sorting, quicksort is often the go-to choice due to its efficiency on average and low space complexity.

Conclusion

We‘ve explored three advanced sorting algorithms – merge sort, quicksort, and radix sort. Each has its strengths and weaknesses in terms of time complexity, space complexity, and applicability. Understanding these algorithms and their tradeoffs is crucial for any programmer working with large datasets.

While it‘s unlikely you‘ll have to implement these algorithms from scratch in a real-world project (most languages have built-in sorting functions), knowing how they work under the hood can help you make informed decisions about which one to use in a given situation.

So the next time you‘re faced with a sorting problem, remember – don‘t just resort to the basic quadratic sorts. Consider leveraging the power of these advanced algorithms. Happy sorting!