Algorithms 101: how to use Merge Sort and Quicksort in JavaScript

This article was written by Jerry Ejonavi and was originally published at Educative, Inc.

---

Sorting in programming involves placing elements in a list or an array in a certain order. Efficient sorting is important for optimizing other algorithms that require input data to be in sorted lists.

While you may not be required to implement a sorting algorithm in your day-to-day as a software developer, it’s important to know how some of these algorithms work internally. These are common for coding interviews and make you a more efficient developer.

In today’s article, we will explore two of the most popular sorting algorithms, Merge sort and Quicksort. These are essential to your foundations in computer science and optimization of code.

Today, we will learn:

• Introduction to sorting algorithms
• Merge Sort algorithm
• Quicksort algorithm
• What to learn next

---

Introduction to sorting algorithms

A sorting algorithm is an algorithm used to reorder items in a list or an array according to a specific requirement. For example, sorting algorithms can organize an array of items from smallest to largest.

An efficient sorting algorithm is important for optimizing the efficiency of other algorithms (such as search and compression algorithms).

Sorting algorithms are made up of a series of instructions. They take an array or list as an input, performs operations, and output a sorted array.

There are a number of popular sorting algorithms. The nine most popular are:

• Bubble sort
• Insertion sort
• Merge sort
• Quicksort
• Selection sort
• Counting sort
• Bucket sort
• Radix sort
• Heapsort

---

Merge Sort algorithm

Merge sort is an efficient, general-purpose, comparison-based sorting algorithm. It works by recursively dividing an array into two equal halves, sorting and then merging each sorted half.

Take an array [10, -1, 2, 5, 0, 6, 4, -5]. Here is how merge sort would approach it.

Merge sort and Quicksort implementations are examples of a divide and conquer algorithm. Broadly speaking, a divide and conquer algorithm has the following parts:

• Divide: This involves dividing the problem into subproblems
• Conquer: recursively process sub problems until each one is solved
• Combine: combine solved sub problems to give a solution to the original problem

Merge sort can be used for all sorts of problems. The three most common applications of merge sort are sorting linked lists in O(nLogn) time, an Inversion Count Problem, and External Sorting.

Implementation in JavaScript

Below is the code implementation of a Merge sort algorithm in JavaScript. The algorithm consists of two functions:

• The mergeSort() function, which takes care of partitioning the arrays
• The merge function, which merges the separate arrays

function mergeSort(array) {
  if (array.length === 1) {
    return array;
  }
  const middle = Math.floor(array.length / 2);
  const left = array.slice(0, middle);
  const right = array.slice(middle);
  return merge(
     mergeSort(left),
     mergeSort(right)
  );
}

function merge(left, right) {
 let result = [];
 let leftIndex = 0;
 let rightIndex = 0;

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

 return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

Let’s try to break down what is happening:

1. If the array has only one element, we return the array and terminate (Base case)
2. Otherwise, we split the array into two halves that are as equal in length as possible (Divide)
3. Using recursion, we sort both arrays using the mergeSort() function. (Conquer)
4. Finally, we merge the two sorted arrays and return the result. (Combine)

So, take the array we used an an example above. Let's see how we would implement merge sort in JavaScript code.

function mergeSort (unsortedArray) {
  if (unsortedArray.length <= 1) {
    return unsortedArray;
  }
  // In order to divide the array in half, we need to find middle
  const middle = Math.floor(unsortedArray.length / 2);

  const left = unsortedArray.slice(0, middle);
  const right = unsortedArray.slice(middle);

  // Use recursion to combine the left and right
  return merge(
    mergeSort(left), mergeSort(right)
  );
}

Time and space complexity

Merge sort has a guaranteed time complexity of O(nlogn) time, which is significantly faster than the average and worst-case running times of several other sorting algorithms. Merge sort is a stable sort with a space complexity of O(n).

• Auxiliary Space: O(n)
• Algorithmic Paradigm: Divide and Conquer
• Sorting in Place: No
• Stable: Yes

Comparison with other sorting algorithms

Merge sort is marginally slower than quicksort in practice. It is also not as space-efficient as the in-place implementation of Quicksort. MergeSort is generally preferred over QuickSort for Linked Lists, due to difference in memory allocation.

---

Quicksort algorithm

Like Merge Sort, QuickSort is a Divide and Conquer algorithm, but it works a bit differently.
Quicksort starts by selecting a pivot element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

Quicksort algorithm doesn’t use any extra space, as the sorting is done in-place.

There are several ways that this algorithm can choose a pivot element.

• Pick first element as pivot
• Pick last element as pivot
• Pick a random element as pivot
• Pick median as pivot

Implementation in JavaScript

The key process below is our partition function, which chooses our pivot. In this implementation, this is done using the Hoare Partition scheme, which works by initializing two indices that start at the ends of the array. The indices move toward each other until an inversion is found.

An inversion is a pair of elements, one greater than or equal to the pivot, one less than or equal, that are in the wrong order relative to each other. The inverted values are then swapped and the process is repeated.

Picking a good pivot is the key for a fast implementation of Quicksort. In practice, Quicksort algorithms use a randomized pivot, which has an expected time complexity of O(n log n).

function partitionHoare(array, left, right) {
  const pivot = Math.floor(Math.random() * (right - left + 1) + left);
  while (left <= right) {
    while (array[left] < array[pivot]) { 
       left++;
    } 
    while (array[right] > array[pivot]) {
      right--;
    }
    if (left <= right) {
      [array[left], array[right]] = [array[right], array[left]];
    }
  }
  return left;
}

function quicksort(array, left, right) {
  left = left || 0;
  right = right || array.length - 1;
  const pivot = partitionHoare(array, left, right);

  if (left < pivot - 1) {
     quicksort(array, left, pivot - 1);
  }
  if (right > pivot) {
     quicksort(array, pivot, right);
  }
  return array;
}

Time Complexity

Quicksort algorithm has a time complexity of O(n log n). In the worst case, this becomes O(n2). The space used by Quicksort depends on the version used.

The in-place version of Quicksort has a space complexity of O(log n), even in the worst case, while the average-case space complexity is O(n)O(n).

• Algorithmic Paradigm: Divide and Conquer
• Sorting in Place: Yes
• Stable: Default is not stable

Comparison with other sorting algorithms

While the average and best-case run time of Quicksort is equal to that of other algorithms such as Merge Sort, a well-implemented Quicksort will have much lower constant factors than other sorting algorithms.

In practice, Quicksort is often faster than merge sort.

In the case of Quick Sort, in its general form is an in-place sort (i.e. it doesn’t require any extra storage). Merge sort requires O(N) extra storage, where N denotes the array size which may be quite large.

---

What to learn next

Sorting is the basis of many complex programming solutions. Though it may seem like a simple concept, it is very crucial for a sorting algorithm to be efficient and fast.

In practice, a sorting algorithm’s efficiency or speed may sometimes depend on the type of data-set being sorted. You should look into the following algorithms next:

• Insertion Sort
• Bubble Sort
• Selection Sort
• Heapsort
• Bucket Sort

To get started with these concepts, check out Educative's learning path Ace the Front end Interview. You'll review all the key concepts you need to be familiar with in CSS, HTML, and JavaScript, practicing and diving deep into dozens of real questions. By the time you’re done, you’ll be able to tackle anything that comes your way on the front-end interviews.

Happy learning!

Continue reading about JavaScript

• JavaScript Array Methods: how to use map and reduce
• 7 JavaScript data structures you must know
• 15 JavaScript Tips: best practices to simplify your code