Sorting is a very classic problem of reordering items (that can be compared, e.g. integers, floating-point numbers, strings, etc) of an array (or a list) in a certain order (increasing, non-decreasing, decreasing, non-increasing, lexicographical, etc).

When an (integer) array A is sorted, many problems become easy (or easier):

• Searching for a specific value v in array A,
• Finding the min/max or the k-th smallest/largest value in (static) array A,
• Testing for uniqueness and deleting duplicates in array A,
• Counting how many time a specific value v appear in array A,
• Set intersection/union between array A and another sorted array B,
• Finding a target pair x ∈ A and y ∈ A such that x+y equals to a target z, etc.

• Sorting numbers from smallest to largest
• Sorting names alphabetically
• Sorting movies based on release year
• Sorting movies based on revenue

They are called comparison-based as they compare pairs of elements of the array and decide whether to swap them or not.

These three sorting algorithms are the easiest to implement but also not the most efficient, as they run in O(N2).

• Bubble Sort
• Selection Sort
• Insertion Sort
• Merge Sort (recursive implementation)
• Quick Sort (recursive implementation)
• Random Quick Sort (recursive implementation)

• Counting Sort
• Radix Sort

A sorting algorithm where the largest values bubble up to the top!

This sort has quadratic time complexity in all cases.

• Start looping from with a variable called i the end of the array towards the beginning
• Start an inner loop with a variable called j from the beginning until i - 1
• Compare a pair of adjacent items (a, b),
• If arr[j] is greater than arr[j+1], swap those two values!
• By now, the largest item will be at the last position.
• Return the sorted array

function bubbleSort(arr){
	// Variables
	var noSwaps;

	// Loop over an array from end to start
	for(var i = (arr.length-1); i >= 0; i--){
		noSwaps = true;

		// Inner loop from start to i
		for(var j = 0; j < i; j++){
			// If current element is greater than next element than do swapping
			if(arr[j] > arr[j+1]){
				noSwaps = false;
				var temp = arr[j+1];
				arr[j+1] = arr[j];
				arr[j] = temp;
			}
		}

		// If there is no swapping than break the loop
		if(noSwaps){
			break;
		}
	}
	return arr;
}
console.log(bubbleSort([8,1,2,3,4,5,6,7]));

Similar to bubble sort, but instead of first placing large values into sorted position, it places small values into sorted position.

Selection sort works by selecting the minimum value in a list and swapping it with the first value in the list. It then starts at the second position, selects the smallest value in the remaining list, and swaps it with the second element. It continues iterating through the list and swapping elements until it reaches the end of the list. Now the list is sorted.

Selection sort has quadratic time complexity in all cases.

• Store the first element as the smallest value you've seen so far.
• Compare this item to the next items in the array until you find a smaller number.
• If a smaller number is found, designate that smaller number to be the new "minimum" and continue until the end of the array.
• If the "minimum" is not the value (index) you initially began with, swap the two values.
• Repeat this with the next element until the array is sorted.

function selectionSort(arr){
	// Loop over an array from start to end
	for(var i = 0; i < arr.length; i++){
		// Store the i element as the smallest index
		var lowest = i;

		// Inner loop from next element to end
		for(var j = (i+1); j < arr.length; j++){
			// Compare value of smallest index to the value of next elements
			// Update the smallest index, if true
			if(arr[j] < arr[lowest]){
				lowest = j;
			}
		}

		// If i is not equal to lowest index than do swapping
		if(i !== lowest){
			var temp = arr[i];
			arr[i] = arr[lowest];
			arr[lowest] = temp;
		}
	}
	// return
	return arr;
}
console.log(selectionSort([0,2,34,12,10,19,22]));

Builds up the sort by gradually creating a larger left half which is always sorted

• Start by picking the second element in the array
• Now compare the second element with the one before it and swap if necessary.
• Continue to the next element and if it is in the incorrect order, iterate through the sorted portion (i.e. the left side) to place the element in the correct place.
• Repeat until the array is sorted.

function insertionSort(arr){
    // Loop over an array from second element to end
    for(var i = 1; i < arr.length; i++){
        // Cuurent value
        var currentVal = arr[i];

        // Inner loop from one element before of i to start of an array
        // Compare the currentVal to one before and do swapping
        for(var j = i - 1; j >= 0 && arr[j] > currentVal; j--){
            arr[j+1] = arr[j];
        }

        // do replace
        arr[j+1] = currentVal;
    }

    // Return sorting array
    return arr;
}
console.log(insertionSort([2,1,9,76,4]));

It's a combination of two things - merging and sorting!

Merge sort uses a divide-and-conquer, recursive methodology to sort an array. Exploits the fact that arrays of 0 or 1 element are always sorted.

Works by decomposing an array into smaller arrays of 0 or 1 elements, then building up a newly sorted array

Merge sort is an efficient sorting method, with time complexity of O(n log(n)). This algorithm is popular because it is performant and relatively easy to implement.

• Break up the array into halves until you have arrays that are empty or have one element
• Once you have smaller sorted arrays, merge those arrays with other sorted arrays until you are back at the full length of the array
• Once the array has been merged back together, return the merged (and sorted!) array

In order to implement merge sort, it's useful to first implement a function responsible for merging two sorted arrays

Given two arrays which are sorted, this helper function should create a new array which is also sorted, and consists of all of the elements in the two input arrays

This function should run in O(n + m) time and O(n + m) space and should not modify the parameters passed to it.

• Create an empty array, take a look at the smallest values in each input array
• While there are still values we haven't looked at...
  • If the value in the first array is smaller than the value in the second array, push the value in the first array into our results and move on to the next value in the first array
  • If the value in the first array is larger than the value in the second array, push the value in the second array into our results and move on to the next value in the second array
  • Once we exhaust one array, push in all remaining values from the other array

// Helper method
function mergeArr(arr1, arr2){
	// Create variables
	var result = [];
	var i = 0;
	var j = 0;

	// Loop over both array and store values in result
	while(i < arr1.length && j < arr2.length){
		if(arr2[j] > arr1[i]){
			result.push(arr1[i]);
			i++;
		}else{
			result.push(arr2[j]);
			j++;
		}
	}

	// Check if array is exaxuted and push rest values in result
	while(i < arr1.length){
		result.push(arr1[i]);
		i++;
	}
	while(j < arr2.length){
		result.push(arr2[j]);
		j++;
	}

	// Return sorted array
	return result;
}

// Sorting algorithm with recursion
function mergeSort(arr){
	// Base condition
	if(arr.length <= 1){
		return arr;
	}

	// Change input and recursion
	let mid = Math.floor(arr.length / 2);
	let left = mergeSort(arr.slice(0, mid));
	let right = mergeSort(arr.slice(mid));

	// Return merged and sorted result
	return mergeArr(left, right);
}
console.log(mergeSort([1,24,9,6,99,251,152]));

Like merge sort, exploits the fact that arrays of 0 or 1 element are always sorted

Works by selecting one element (called the "pivot") and finding the index where the pivot should end up in the sorted array

Once the pivot is positioned appropriately, quick sort can be applied on either side of the pivot

In order to implement merge sort, it's useful to first implement a function responsible arranging elements in an array on either side of a pivot.

• Given an array, this helper function should designate an element as the pivot.
• It should then rearrange elements in the array so that all values less than the pivot are moved to the left of the pivot, and all values greater than the pivot are moved to the right of the pivot.
• The order of elements on either side of the pivot doesn't matter!
• The helper should do this in place, that is, it should not create a new array.
• When complete, the helper should return the index of the pivot

• The runtime of quick sort depends in part on how one selects the pivot
• Ideally, the pivot should be chosen so that it's roughly the median value in the data set you're sorting
• For simplicity, we'll always choose the pivot to be the first element (we'll talk about consequences of this later)

• It will help to accept three arguments: an array, a start index, and an end index (these can default to 0 and the array length minus 1, respectively)
• Grab the pivot from the start of the array
• Store the current pivot index in a variable (this will keep track of where the pivot should end up)
• Loop through the array from the start until the end
  • If the pivot is greater than the current element, increment the pivot index variable and then swap the current element with the element at the pivot index
• Swap the starting element (i.e. the pivot) with the pivot index
• Return the pivot index

• Call the pivot helper on the array
• When the helper returns to you the updated pivot index, recursively call the pivot helper on the subarray to the left of that index, and the subarray to the right of that index
• Your base case occurs when you consider a subarray with less than 2 elements

function swap(arr, i, j){
	var temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}
function pivot(arr=[], start=0, end=(arr.length+1)){
	// Declare variables
	var pivotElement = arr[start];
	var swapIdx = start;
	// Loop
	for(var i=(start+1); i<=end; i++){
		if(pivotElement > arr[i]){
			swapIdx++;
			swap(arr, i, swapIdx);
		}
	}
	// Final swap
	swap(arr, start, swapIdx);
	// Return swap index,
	return swapIdx;
}
function quickSort(arr, left = 0, right = (arr.length-1)){
	// Base condition
	if(left < right){
		var pivotIdx = pivot(arr, left, right);
		// Left
		quickSort(arr, left, pivotIdx-1);
		// Right
		quickSort(arr, pivotIdx+1, right);
	}

	// Return sorted array
	return arr;
}
console.log(quickSort([100, 4, -3, 9, 2, 1, 5]));

Radix sort is a special sorting algorithm that works on lists of numbers

It never makes comparisons between elements!

It exploits the fact that information about the size of a number is encoded in the number of digits.

More digits means a bigger number!

Time Complexity is O(nk)

• n - length of array
• k - number of digits(average)

In order to implement radix sort, it's helpful to build a few helper functions first:

• getDigit(num, place)
  • returns the digit in num at the given place value
• digitCount(num)
  • returns the number of digits in num
• mostDigits(nums)
  • Given an array of numbers, returns the number of digits in the largest numbers in the list

• Define a function that accepts list of numbers
• Figure out how many digits the largest number has
• Loop from k = 0 up to this largest number of digits
• For each iteration of the loop:
  • Create buckets for each digit (0 to 9)
  • place each number in the corresponding bucket based on its kth digit
• Replace our existing array with values in our buckets, starting with 0 and going up to 9
• return list at the end!

// Helpers
function getDigit(num, i) {
	return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;
}
function digitCount(num) {
	if(num === 0){
		return 1;
	}
	return Math.floor(Math.log10(Math.abs(num))) + 1;
}
function mostDigits(nums) {
	let maxDigits = 0;
	for(let i = 0; i < nums.length; i++){
		maxDigits = Math.max(maxDigits, digitCount(nums[i]));
	}
	return maxDigits;
}

// Sorting
function radixSort(nums){
	// Declare variables
	let maxDigitsCount = mostDigits(nums);

	// Loop over maxDigitsCount
	for(var k=0; k<maxDigitsCount; k++){
		let digitBuckets = Array.from({length: 10}, () => []);

		// Loop over every number
		for(var i=0; i<nums.length; i++){
			let digit = getDigit(nums[i], k);
			digitBuckets[digit].push(nums[i]);
		}

		// Concat
		nums = [].concat(...digitBuckets);
	}

	// Return sorted array
	return nums;
}
radixSort([32,345,2,89,6,9]); // [2, 6, 9, 32, 89, 345]