4 ms·
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 yo
by tantaman 14y ago
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.
- Inufu 14y agoHere's a solution that merges in place without any sorting: https://gist.github.com/Mononofu/5029975 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 http://dl.dropbox.com/u/2135523/2013022517.png
- tantaman 14y agoYep. 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.
- PeterisP 14y agoMerge 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.