# JavaScript Merge Sort

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

1. 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
2. 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
}``````