Merge Sort (JS Example)

Note: This is not a "professionally written" post. This is a post sharing personal notes I wrote down while preparing for FAANG interviews.

Merge Sort Breakdown
  • Worst Complexity: n*log(n)
  • Average Complexity: n*log(n)
  • Best Complexity: n*log(n)
  • Space Complexity: n
  • Method: Merging
  • Stable: Yes
  • Merge Sort Explained
    In computer science, merge sort is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output.
    Merge Sort Notes
  • Divide & Conquer sorting algorithm
  • Stable sorting algorithm
  • Quick sort has a better space complexity than merge sort
  • Merge sort is a stable sort while quick sort is unstable
  • Merge sort's worst case time complexity is better than quick sorts
  • Merge Sort JavaScript Implementation
    /*----------------------------------------------------------
     |   Merge Sort
     *----------------------------------------------------------
     |
     |   Time Complexity 
     |      . Best: O(n log n)
     |      . Aver: O(n log n)
     |      . Worst: O(n log n) 
     | 
     |   Space Complexity
     |      . O(n)
     |
     |   Divide And Conquer Sort
     |   Stable Sort
     |   Quick Sort Has A Better Space Complexity Than Merge Sort
     |   Merge Sorts Worst Case Time Complexity Is Better Than Quick Sort
     |   Merge Sort is A Stable Sort While Quick Sort is an Unstable Sort
     */
    
    const merge = (left = [], right = [], merged = []) => {
      let compare = ([a], [b]) => (a ?? b+1) < (b ?? a+1)
      let side = () => compare(left, right) ? left : right
    
      while (left.length && right.length) merged.push(side().shift())
      while (right.length) merged.push(right.shift())
      while (left.length) merged.push(left.shift())
    
      return merged
    }
    
    const MergeSort = (items = []) => {
      if (items.length <= 1) return items
    
      const middle = Math.floor(items.length/2)
    
    
      return merge(
        MergeSort(items.slice(0, middle)),
        MergeSort(items.slice(middle, items.length))
      )
    }
    
    
    module.exports = MergeSort

    FAANG Study Resource: Cracking the Coding Interview
    (Google Recommended)

    42

    This website collects cookies to deliver better user experience

    Merge Sort (JS Example)