## A Divide and Conquer Sorting Algorithm

O(n log n) - Linearithmic time

What is `O(n log n)`?

`O(n log n)` is a Log-linear algorithm with a complexity rank of  close to fair, which works by merging two functions, one of which being of `0(n) linear` time complexity and the other being of  `0(log n)` (binary search) time complexity.

EX:

``````let arr = [ 7, 3, 9, 10, 4, 0, 2, 1 ];

function merge(left,right){ //linear runtime O(n) => based on arr length
let result = [];

while(left.length || right.length) {

if(left.length && right.length) {
if(left < right) {
result.push(left.shift());
} else {
result.push(right.shift());
}
} else if(left.length) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
return result;

}

// similar to binary search => divides arr into 1/2 on each iteration
// Logarithmic runtime O(log n)
function mergeSort(arr = []){
if(arr.length <= 1){
return arr;
}

// Divide array in 1/2
const mid = arr.length / 2; // create pivot @ index 4 in this case
const left = arr.slice(0, mid); // [ 7, 3, 9, 10 ]
const right = arr.slice(mid, arr.length); // [ 4, 0, 2, 1 ]

// recursively use merge() => ie., calls itself until an exit condition
// is met => based on array.length
return merge(mergeSort(left), mergeSort(right));
}

// 2 functions are merged => Log-linear O(n log n) => o(n) * 0(log n)
// ..better than quadratic O(n^2), but not as good as 0(n) linear,
// O(log n) logarithmic, or O(1) constant
mergeSort(arr); // [ 0, 1, 2, 3, 4, 7, 9, 10 ]``````