DEV Community

loading...

Discussion on: JavaScript ES6 one-liners: merge two sorted lists

Collapse
sergeis profile image
Sergei Author • Edited

Because list merging is a step in merge-sort, so this becomes a chicken-and-egg problem if you write your own merge-sort. Certainly if you are allowed to used sort, there is no reason to explicitly merge lists element-by-element. Also, sort is O(n log(n)) and merging is O(n) where n is the combined length of the lists. Well, it is supposed to be O(n) when properly implemented, the shift function I used is a poor choice, since its complexity is O(n) not O(1), as pointed out by Theofanis in the other reply.