Bubble Sort

Principle: Repeatedyl compare adjacent items and swap them if they are in the wrong order, so that larger elements "bubble" toward the end.

Implementation:

Array.prototype.bubbleSort = function() {
  var size = this.length;
  for (var i = 0; i < size; i++) {
    for (var j = 0; j < size - 1 - i; j++) {
      if (this[j] > this[j + 1]) {
        exchange(this, j, j + 1); // exchange swaps two elements
      }
    }
  }
};

Notice that the inner loop stops one step earlier after each pass because the largest element has already settled at the end.

Time complexity is O(n²). You can experiment with the process at xSortLab.

Sorting ten arrays of 10,000 random items each took 28.7 seconds.

Selection Sort

Principle: Find the smallest element in the unsorted portion and swap it with the element at the current position, then repeat for the next position.

Implementation:

Array.prototype.selectSort = function() {
  var size = this.length, minPos;
  for (var i = 0; i < size - 1; i++) {
    minPos = i;
    for (var j = i; j < size; j++) {
      if (this[minPos] > this[j]) minPos = j;
    }
    if (i !== minPos) exchange(this, i, minPos); // exchange swaps two elements
  }
};

Time complexity is O(n²).

Sorting ten arrays of 10,000 random items each took 17.7 seconds.

Insertion Sort

We cover direct insertion sort here. The first element is considered sorted; each subsequent element is inserted into its correct position within the sorted portion.

{{a1}，{a2，a3，a4，…，an}}

Implementation:

Array.prototype.insertSort = function() {
  var size = this.length, position, current;
  for (var i = 1; i < size; i++) {
    position = i;
    current = this[i]; // element to be inserted
    while (position > 0 && this[position - 1] > current) {
      this[position] = this[position - 1];
      position--;
    }
    this[position] = current; // perform the insertion
  }
};

Time complexity is O(n²).

Sorting ten arrays of 10,000 random items each took 8 seconds.

Merge Sort

Merge sort is a real-world, efficient algorithm. Many browsers use either merge sort or quick sort for Array.prototype.sort (V8 may use insertion sort for very short arrays).

Principle: Apply divide-and-conquer recursively — split the array into halves until subarrays contain a single element, then merge them back in sorted order.

During merging, compare the first elements of two sorted arrays, take the smaller one and push it into the result array.

Implementation:

function combine(leftArr, rightArr) {
  var result = [];
  while (leftArr.length && rightArr.length) {
    if (leftArr[0] < rightArr[0]) {
      result.push(leftArr.shift());
    } else {
      result.push(rightArr.shift());
    }
  }
  return result.concat(leftArr).concat(rightArr);
}

function mergeSort(arr) {
  if (arr.length === 1) return arr;
  var middle = Math.floor(arr.length / 2);
  var leftHalf = arr.slice(0, middle);
  var rightHalf = arr.slice(middle);
  return combine(mergeSort(leftHalf), mergeSort(rightHalf));
}

Time complexity is O(n log n).

Merge sort dramatically improves performance on large datasets.

Quick Sort

Principle: Choose a pivot (often the middle element). Partition the array so that elements smaller than the pivot go to the left and larger ones go to the right, then recursively sort the partitions.

Implementation:

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

  var pivotIdx = Math.floor(arr.length / 2);
  var pivotVal = arr.splice(pivotIdx, 1)[0];
  var smaller = [];
  var greater = [];

  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < pivotVal) {
      smaller.push(arr[i]);
    } else {
      greater.push(arr[i]);
    }
  }

  return quickSort(smaller).concat([pivotVal], quickSort(greater));
}

This implementation is inspired by Ruan Yifeng’s article: http://www.ruanyifeng.com/blog/2011/04/quicksort_in_javascript.html

Time complexity is O(n log n).

Its performance is very close to merge sort. For a deeper comparison, see this Stack Overflow dicsussion.