Sorting

Merge Sort

The algorithm uses a technique called divide and conquer, this algorithms starts by dividing the dataset into smaller dataset until each smaller dataset have only one element in it and then start building by combining the smaller dataset into bigger dataset from the lowest value to the larger value until there are no small datasets left and finally we return a sorted dataset.video shows how the algorithm works

Big(O)

| | speed | | -------- | ------- | | Best | O(n logn) | | Average | O(n logn) | | Worst | O(n logn) |

Implementation

We have two implementations: the first one is recursive and the second is iterative. We are going to use the recursive approach. Recursion is when the function call itself

function mergeSort(data){
  if(data.length<=1){
    return data
  }
  let mid = Math.floor(data.length/2);
  let left = data.slice(0,mid);
  let right = data.slice(mid);
  return merge(mergeSort(left),mergeSort(right))
}

function merge(left,right){
  let result = [];
  let i = 0;
  let j = 0;
  while(i<left.length && j<right.length){
    if(left[i]<right[j]){
      result.push(left[i]);
      i++;
    }else{
      result.push(right[j]);
      j++;
    }
  }
  while(i<left.length){
    result.push(left[i]);
    i++;
  }
  while(j<right.length){
    result.push(right[j]);
    j++;
  }
  return result
}