Hacker News Reader

Comment by tantaman | Hacker News Reader

The issue is merging the arrays, not sorting them. How do you MERGE two arrays without allocating a new one that is big enough to contain them both?

If all you need to do is print what the result of the merge would be then sure, a solution does exist.

View on HN

Here's a solution that merges in place without any sorting: https://gist.github.com/Mononofu/5029975

The basic idea is to use the (unused) beginning of array b as swap space for the beginning of array a. This swap space needs to be shifted around, so it's of course O(n^2). Still, it was fun to write.

If you have termcolor installed ('sudo easy_install termcolor' on ubuntu), you'll see the arrays a and b as well as the swap space highlighted in color for each step. Example: http://dl.dropbox.com/u/2135523/2013022517.png

Yep. I did say that that solution exists ^^. I just said that you couldn't do it without creating something to hold the merged result. Your solution does allocate a buffer to hold the merged result: `self.array = self.a + self.b`

I wasn't saying you can't sort arrays in place (quicksort). I was saying you can't merge them in place. Somebody has to grow.

Merge them in-place - if the inital array A had 400 items and array B 600 items, then put the sorted first 400 items in original array A and the last 600 items in array B.

For any practical purpose that's as good as a contiguous array, and in embedded systems you might even make so that the initial two arrays are already contiguous in memory.

Reply on news.ycombinator.com