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

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.

• 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

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.

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)$.

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, sorting is one of the many types of algorithms tested in coding interview.

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
• Algorithms 101: How to check if a string is a palindrome