JavaScript Merge Sort

Merge Sort is basically a divide and conquer algorithm. It consists of 2 parts:

Sorting Part
1. If array length is 1 then return original array
2. Divide array into 2 equal parts (where possible) and recursively sort them
3. Merge sorted parts
Merge Part
1. Merge 2 arrays by taking lowest element from arrays' heads

Merge function splits array recursively until there is only 1 element left in each subarray and then merges sorted pairs of subarrays:

function mergeSort(arr){
  // If length is 1 return original
  if (arr.length <= 1) return arr

  // Split array into 2
  var arr1 = arr.slice(0, Math.ceil(arr.length/2))
    , arr2 = arr.slice(Math.ceil(arr.length/2))

  // Recursively sort each subarray
  arr1 = mergeSort(arr1)
  arr2 = mergeSort(arr2)

  // Merge sorted subarrays
  return mergeSortMerge(arr1, arr2)
}

Merge function merges 2 sorted arrays and returns a sorted array:

function mergeSortMerge(arr1, arr2){
  // Revert subarrays so that lowest element are at end
  arr1.reverse(); arr2.reverse();

  // Init variables
  var arr = []
    , l1 = arr1.length - 1
    , l2 = arr2.length - 1

  // While still have elements to process
  while(l1 >= 0 || l2 >= 0){
    // If both arrays have elements
    if (l1 >= 0 && l2 >= 0) {
      // Take smallest value
      if (arr1[l1] > arr2[l2]) {
        arr.push(arr2[l2])
        l2 -= 1
      } else {
        arr.push(arr1[l1])
        l1 -= 1
      }
    // If elements left only in first subarray
    } else if (l1 >= 0) {
      arr.push(arr1[l1])
      l1 -= 1
    // If elements left only in secnd subarray
    } else {
      arr.push(arr2[l2])
      l2 -= 1
    }
  }
  return arr
}