-
-
Notifications
You must be signed in to change notification settings - Fork 47.7k
Merge Implementation Issue in Merge Sort #11434
-
I think popping from the beginning of the list might be very expensive here and can cause the sorting complexity to deteriorate to O(n^2)
Beta Was this translation helpful? Give feedback.
All reactions
Replies: 1 comment 1 reply
-
Popping from the front can indeed be expensive for large lists. Bu int his case we are popping from the list which is referenced in the merge function which is called recursively thus it doesn't affect the overall time complexity.
In case we are popping without recursion it can prove to be expensive
Beta Was this translation helpful? Give feedback.
All reactions
-
Not sure what you mean by that but if you consider the last merge pass where you merge two sorted sublists of size N/2, popping from the front of the list in this pass alone immediately yields in O(N^2) overhead.
Beta Was this translation helpful? Give feedback.