Merge sort space is O(n) not O(1)

tsiege / Tech-Interview-Cheat-Sheet

Studying for a tech interview sucks. Here's an open source cheat sheet to help

MIT License

4.29k stars 983 forks source link

Merge sort space is O(n) not O(1) #18

Open rszymula opened 3 years ago

rszymula commented 3 years ago

Need to update merge sort space complexity to O(n)

It was odd to me that merge sort stats here are "better" than quick sort in every way - whereas Quicksort is used everywhere in practice, not Mergesort.

Why is QuickSort favourable over MergeSort in practice? https://www.reddit.com/r/computerscience/comments/6krpz7/why_is_quicksort_favourable_over_mergesort_in/

Quicksort is used bc is has better space complexity than merge. Merge should be O(n)

sharifsonic commented 3 years ago

just noticed the same. PLease update

tsiege commented 2 years ago

Happy to accept pull requests