Data Structures and Algorithms in Javascript - Part 2

This is a continuation of my post on Data Structures and Algorithms in Javascript...to get you started.

In Part 2, we will cover

• Merge Sort
• Binary Search

Merge Sort

Merge sort is a divide and conquer algorithm. Merge sort works as follows:

• Divide the unsorted list into n sublists, each containing one element (a list of one element is considered sorted).
• Repeatedly merge sublists to produce new sorted sublists (conquer) until there is only one sublist remaining. This will be the sorted list.

let array = [38, 27, 43, 3, 9, 82, 10];

function merge(left, right) {
  let results = [];
  while (left.length && right.length) {
    left[0] < right[0]
      ? results.push(left.shift())
      : results.push(right.shift());
  }
  return [...results, ...left, ...right];
}

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

console.log(mergeSort(array));

Time Complexity: In sorting n objects, Merge sort has an average and worst-case performance of O(n log n).

Binary Search

Binary Search is used to search for an element in sorted arrays. It uses divide and conquer approach. Binary Search works as follows:
To search for target value(num),

• Compare the middle element of the array with num.
• If num equals middle element, its position in the array is returned.
• If num < middle element, the search continues in the lower half of the array.
• If num > middle element, the search continues in the upper half of the array. As the array is sorted, in each iteration the algorithm eliminates the half in which the target value doesn't exist.

let array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];

function _findNumber(arr, left, right, num) {
  let mid = Math.floor((left + right) / 2);
  if (num === arr[mid]) {
    return mid;
  }
  if (left === right) {
    //only one element to be checked and it is not num
    return -1;
  }
  return num > arr[mid]
    ? _findNumber(arr, mid + 1, right, num)
    : _findNumber(arr, left, mid - 1, num);
}

function findNumber(arr, num) {
  if (arr.length === 0) {
    // no elements in array
    return -1;
  }
  return _findNumber(arr, 0, arr.length - 1, num);
}

console.log(findNumber(array, 4));

Time Complexity: O(log n) where n is the number of elements in the array.