There's tons of Sorting Algorithms, however for interviews, being able to implement a select few and explain their time complexity should be enough.
Also check the sorting algorithms used by different languages, to see what they use.
For JavaScript, Mozilla uses Merge Sort, but Chrome uses Quick Sort and Insertion Sort (for smaller arrays).
Implementation
1. Quick Sort
Quick Sort is a Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of Quick Sort that pick pivot in different ways. (e.g. First, Last, Random, or Median Element as pivot)
Keep following aspects in mind while choosing Quick Sort.
- It's an unstable sort, meaning the order for same keys is not guaranteed.
- It requires O(1) extra space as it's an in place sort.
- Best used on Arrays.
- Randomised version of Quick Sort is the most common one.
- The Quick Sort is internal sorting method where the data is sorted in main memory, hence it cannot be used for large data sets.
- Quick Sort exhibits good cache locality and this makes Quick Sort faster than merge sort (in many cases like in virtual memory environment).
function partition(arr, start = 0, end = arr.length - 1) {
// Let's choose the pivot to be the arr[start] element
let pivot = arr[start];
let swapIdx = start;
for (let i = start + 1; i <= end; i++) {
if (arr[i] < pivot) {
swapIdx++;
// Swap current element with the element at the new
// pivot index
[arr[i], arr[swapIdx]] = [arr[swapIdx], arr[i]];
}
}
// Swap the pivot element with the element at the pivot index
[arr[swapIdx], arr[start]] = [arr[start], arr[swapIdx]];
// Return the index of the pivot element after swapping
return swapIdx;
}
// Recursive
function quickSort(arr, left = 0, right = arr.length - 1) {
// Base case is that the left and right pointers don't overlap,
// after which we'll be left with an array of 1 item
if (left < right) {
let pivotIndex = partition(arr, left, right);
// For left subarray, which is everything to the left
// of the pivot element
quickSort(arr, left, pivotIndex - 1);
// For the right sub array, which is everything to the
// right of the pivot element
quickSort(arr, pivotIndex + 1, right);
}
// Return the array, when it's of length 1 i.e, left === right
return arr;
}


2. Merge Sort
Merge Sort is a Divide and Conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.
Keep following aspects in mind while choosing Merge Sort.
- Merge Sort is a stable sort, unlike Quick Sort and Heap Sort, and can be easily adapted to operate on linked lists and very large lists stored on slow-to-access media such as disk storage or network attached storage
- Best used with Linked List, as
- Merging multiple linked list is easier compared to Arrays.
- Merge Sort requires sequential access, and not random.
- It requires O(n) extra space, as it's not an in place sort.
- Merge sort is more efficient and works faster than quick sort in case of larger array size or datasets.
- Merge sort can work well on any type of data sets irrespective of its size.
function merge(arr1, arr2) {
// Make a new array, and 2 pointers to keep track of elements of
// arr1 and arr2
let res = [],
i = 0,
j = 0;
// Loop until either arr1 or arr2 becomes empty
while (i < arr1.length && j < arr2.length) {
// If the current element of arr1 is lesser than that of
// arr2, push arr1[i] and increment i
if (arr1[i] < arr2[j]) {
res.push(arr1[i]);
i++;
} else {
res.push(arr2[j]);
j++;
}
}
// Add the rest of the remining subarray, to our new array
while (i < arr1.length) {
res.push(arr1[i]);
i++;
}
while (j < arr2.length) {
res.push(arr2[j]);
j++;
}
return res;
}
// Recursive merge sort
function mergeSort(arr) {
// Base case
if (arr.length <= 1) return arr;
// Splitting into two halves
let mid = Math.floor(arr.length / 2);
let left = mergeSort(arr.slice(0, mid));
let right = mergeSort(arr.slice(mid));
// merging the two sorted halves
return merge(left, right);
}


3. Insertion Sort
Insertion sort works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.
- Very basic algorithm.
- It's Stable Sorting algorithm.
- In place.
- Not suitable for large data sets.
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
// Start comparing current element with every element before it
for (let j = i - 1; j > -1; j--) {
// Swap elements as required
if (arr[j + 1] < arr[j]) {
[arr[j + 1], arr[j]] = [arr[j], arr[j + 1]];
}
}
}
return arr;
}


4. Heap Sort
Heap Sort is a comparison based sorting technique based on Max Heap. We first place the maximum element at the root and then poll repeatedly till heap is empty.
- It's an unstable sort.
- array-based, space-efficient.
// Create Max Heap
function maxHeap(arr, i) {
const left = 2 * i + 1;
const right = 2 * i + 2;
let max = i;
if (left < arrLength && arr[left] > arr[max]) {
max = left;
}
if (right < arrLength && arr[right] > arr[max]) {
max = right;
}
if (max != i) {
swap(arr, i, max);
maxHeap(arr, max);
}
}
function swap(arr, i, j) {
const temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function heapSort(arr) {
arrLength = arr.length;
for (let i = Math.floor(arrLength / 2); i >= 0; i -= 1) {
maxHeap(arr, i);
}
for (i = arr.length - 1; i > 0; i--) {
swap(arr, 0, i);
arrLength--;
maxHeap(arr, 0);
}
return arr;
}


5. Bubble Sort
Bubble Sort works by repeatedly swapping the adjacent elements if they are in wrong order.
- Very basic algorithm.
- It's Stable Sorting algorithm.
- In place.
- Not suitable for large data sets.
function bubbleSort(arr) {
let noSwaps;
for (let i = arr.length; i > 0; i--) {
noSwaps = true;
for (let j = 0; j < i - 1; j++) {
if (arr[j + 1] < arr[j]) {
// Swap
[arr[j + 1], arr[j]] = [arr[j], arr[j + 1]];
// Make 'noSwaps' false
noSwaps = false;
}
}
// End the iterations if there were no swaps made in one full pass
if (noSwaps) {
break;
}
}
return arr;
}


It's terrible, just explaining that should be enough.
Big O

Choice of Sorting algorithm in an interview is done based on time space trade-offs among other factors.
Algorithm | Time Complexity | Space Complexity | ||
---|---|---|---|---|
Best | Average | Worst | Worst | |
Quick Sort | Ω(n log(n)) | Θ(n log(n)) | O(n^2) | O(log(n)) |
Merge Sort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) | O(n) |
Heap Sort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) | O(1) |
Bubble Sort | Ω(n) | Θ(n^2) | O(n^2) | O(1) |
Insertion Sort | Ω(n) | Θ(n^2) | O(n^2) | O(1) |



Conclusion
In real world, variations of above sorting algorithms are used.
For example Python uses an algorithm called Tim Sort which is a hybrid sorting algorithm, derived from Merge Sort and Insertion Sort, designed to perform well on many kinds of real-world data.
Algorithm | Time Complexity | Space Complexity | ||
---|---|---|---|---|
Best | Average | Worst | Worst | |
Tim Sort | Ω(n) | Θ(n log(n)) | O(n log(n)) | O(n) |
Hope the above resources helped you. Please let me know your thoughts down below.
- Algorithms
- LeetCode
- Tips
- Comparisons
- Interviews
- #Sorting Algorithms
- #JavaScript
Leave a Comment