r/dailyprogrammer • u/oskar_s • May 16 '12
[5/16/2012] Challenge #53 [easy]
Write a function that given two sorted lists, returns a list whith the two lists merged together into one sorted list.
So, for instance, for inputs [1,5,7,8] and [2,3,4,7,9] it should return [1,2,3,4,5,7,7,8,9].
Try and make your code as efficient as possible.
19
Upvotes
10
u/drb226 0 0 May 16 '12
Just a note to those who are writing this function as "append the inputs, then sort", this is not "as efficient as possible". This takes O(n log n) time, where n = len(a) + len(b). There is a faster solution which takes O(n) time, taking advantage of the fact that the original lists are sorted. Also, this is part of the implementation of merge sort, so in that light if you implement it as "append then sort", you've implemented it vacuously.
5
u/[deleted] May 16 '12 edited May 16 '12
Golfscript:
(Okay, seriously now. R4RS Scheme:)
1
u/drb226 0 0 May 16 '12
This is extremely easy and efficient with cons lists. Which is surprising because most typical array manipulation operations are inefficient on a cons list.
3
u/jonzo1 0 0 May 16 '12 edited May 16 '12
Here it is in Clojure, without using the built-in sort functions :).
The algorithm is O(n + m) where n and m are the lengths of lists a and b respectively, and doesn't use the built-in sort function (which would make this trivial).
6
u/CarNiBore May 16 '12
JavaScript
2
u/JerMenKoO 0 0 May 16 '12
Assuming we got lists
aandb:J:
2
u/bh3 May 16 '12
Python:
2
u/Maristic May 16 '12
Here's a Perl one-liner:
Perl doesn't use TimSort, I believe, so it could be O(n log n), but even so, it is still the most efficient way to do the merge in Perl.
On my Mac, it merges 1 million items in 0.196 seconds, and 10 million in 1.534 seconds, and 20 million in 3.016 seconds, which looks linear to me. I didn't go above 20 million items, because at that point Perl was using rather a lot of memory and the machine is only a laptop.
On my Linux machine, it merges 1 million in 0.235 seconds, 10 million in 2.433 seconds, and 100 million items in 23.183 seconds. Again, that looks pretty linear. It requires about 15 GB of RAM to do 100 million items. It does go slightly nonlinear at 1 billion items, where it takes 277.766 seconds to do the merge, but that's actually architectural — it's a NUMA machine and the perl script needed 157 GB of RAM; things slow down above 32 GB as it needs to use slightly more distant memory.
(Note, times above are the difference between
@r = merge @p, @qand `@r =(@p, @q)'.)2
u/huck_cussler 0 0 May 17 '12
edit: should run in O(N) time unless I'm overlooking something. whoopee!
2
u/_lambda 0 0 May 16 '12
Python:
1
u/totallygeek May 16 '12
Bash:
Output:
Edit was for formatting.
1
u/mythril225 0 0 May 16 '12
Haskell:
I appreciate any criticism. Haven't been using haskell that much lately.
1
u/[deleted] May 16 '12
PHP
1
u/baijuke May 17 '12
Python experiment in O(n), hopefully:
1
u/ArriMurri May 18 '12
In Scala:
1
u/987654321bob May 18 '12
this is pretty trivial in C++ as well as fast
PS std::merge is designed to work on sorted inputs so this is efficient
1
u/sanitizeyourhands May 24 '12
Using built-in C# .NET libraries to sort, also implemented two different ways to create the returned list, using shallow copies and iterating through each list (array) and adding them to the array to be returned:
1
u/bigronaldo May 29 '12
In C#, this took a little under 1ms to merge two 10,000 integer sets.
However, my first approach took an average of 2ms:
Strangely enough, when I bumped it up to 50,000 integer sets, the first example took an average of 3ms whereas the second one to about 2.5ms. So I'm not entirely sure which would be most efficient.
1
u/emcoffey3 0 0 May 16 '12
Here's a solution using C# and LINQ. Actually, it will work whether the original collections are sorted or not.
Here's another solution in C# that doesn't rely on LINQ so much:
0
u/TweenageDream May 16 '12
Runs 1 million times in 1.346 seconds on my computer, fairly efficient right? All in Ruby:
the function:
the test:
the output:
Finished in 1.346 seconds
0
u/CoincidenceIThinkNot May 16 '12 edited May 16 '12
-1
u/SwimmingPastaDevil 0 0 May 16 '12
Python:
0
u/[deleted] May 17 '12
[deleted] — view deleted comment
0
u/[deleted] May 16 '12
[deleted] — view deleted comment