## 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[0] < right[0]) {
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 ]
```

## Comments