Comment by PeterisP | Hacker News Reader

Comment by PeterisP | Hacker News Reader

Well, the OP statement "write a function which merges two sorted arrays without allocating any additional memory. Aside from having no real-world value, it’s not actually possible" seems strange.

Ok, any real-world usage might be applicable only in embedded systems which is a fairly narrow domain.

Still, it is a small (easy to describe) problem that can be used to see how the applicant does problem solving for problems without a widely known best/proper solution - and that skill is probably 90% of any serious programming; the remainder is just typing while following an arbitrary syntax which a trained monkey can do.

And the solution definitely exists - depending on how the interviewer wants output, you can either push the result out with a trivial iteration with a pointer on each array; or if the arrays aren't read only, you can sort them in-place with a slightly modified qsort or even bubblesort - both of these approaches don't need to allocate any memory on the heap, just 2 int counters in processor registers or stack.

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.

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.

This is standard undergraduate question in algorithms when I went to college. If you need N log(N) solution, look up in-situ mergesort. If you don't care about the order of algorithm, there are much simpler intuitive ways of doing it.

Assume that you have two sorted arrays A and B. At the end of it, A followed by B needs to be sorted. Here is a simple algorithm:

Sort(A,B):

    if A[0] is greater than B[0], swap A[0] and B[0]. 
        Bubble up B[0] to its right place (that is make B sorted).

   Sort(A+1, B) -- stop if A reached its end.

Naive implementation, such as this is N^2. Leaving it to readers to make it N log(N), which is actually trivial.

That comes to a different point. When I was going to college in Computer science, we had to go through at least three courses in algorithms. We used to hand code most algorithms optimizing for the situation at hand. I suppose the advent of good libraries, and the bottlenecks elsewhere in the systems means that this generation may not find fundamentals of algorithms much use. Instead, they may find concepts in abstraction, higher order functions etc more useful.

Reply on news.ycombinator.com