Timeline for Merge two sorted lists

6 events

when toggle format	what	by	license	comment
Jun 17, 2020 at 9:04	history	edited	Community Bot		Commonmark migration
Apr 8, 2014 at 23:38	comment	added	izzyg		Actually, append and extend are implemented differently in python than += is. += creates a new list, while .append and .extend modify an existing one.
Apr 8, 2014 at 22:53	comment	added	Wrzlprmft		I didn’t even know until now that lists aren’t implemented as lists in Python and even then `pop(0)` can be implemented in O(1) and `+=` can at least be implemented better than O(n) (see the link). By the way, your solution uses `+=` (i.e., `append` and `extend`) as often as mine. Anyway, all that is an implementation question (as far as I know), so in a (fictional) Python implementation, where lists are implemented as lists, my function is O(n). Finally your question required the algorithm to be O(n), and mine is.
Apr 8, 2014 at 21:24	comment	added	izzyg		This is definitely not O(n). .pop(0) and += are both O(n) operations you do O(n) times.
Apr 8, 2014 at 18:47	history	edited	Wrzlprmft	CC BY-SA 3.0	added 152 characters in body
Apr 8, 2014 at 18:40	history	answered	Wrzlprmft	CC BY-SA 3.0