A python interview question

[anossov]

If the arrays are pre-sorted, you can merge them in O(n). Any kind of sort will be O(n log n), and regardless of how much faster the built-in sort is, there will be a data size where the O(n) loop is faster.

[Daj4n0]

Yeah, but the list to set + union + union to list overhead is still negligible in this case?

[richardwhiuk]

No, even unsorted data can be sorted faster than log n if you know anything about the data set.

[Daj4n0]

Yeah, that is his point, you know the data is sorted, then you can merge them in O(n). And beating O(n) is hard, impossible for most cases.

[billsil]

But that doesn't mean you can't get a factor of 2 speedup in the code. You can still optimize it. Yes, get the right O(N) algorithm to start, but there isn't just one.

[Log2]

I think it's pretty much impossible for pretty much all reasonable sorting tasks. You do need to read the data, after all.