Merge Implementation Issue in Merge Sort

[Robertation256]

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)

[Mayureshd-18]

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

[Robertation256]

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.