Note: This is not a "professionally written" post. This is a post sharing personal notes I wrote down while preparing for FAANG interviews.
See all of my Google, Amazon, & Facebook interview study notes
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)
Top comments (1)