In-place sort an array with 2 sorted sub-arrays
algorithm, sorting
Solution
See http://comjnl.oxfordjournals.org/content/38/8/681.full.pdf+html for a linear time algorithm for solving this exact problem, and an indication of how much effort was spent coming up with that solution.
My guess is that the interviewer had some cute answer that they thought worked, which doesn't really. The second best guess is that they didn't specify the complexity for a reason.
In an interview I would actually have said, "I don't know how to do this efficiently, though I am sure that there is research on that question. But here is an inefficient answer." Then I'd do something that will clearly work.
Problem
[This is an interview question. I couldn't find a duplicate.] An array contains two sub- sorted arrays. Give an inplace algorithm to sort two sub arrays. for ex: I/P: 1 4 5 7 8 9 2 3 6 10 11 O/P: 1 2 3 4 5 6 7 8 9 10 11 I thought in terms of in-place merge sort, insertion sort (since the sub-arrays are already sorted) and in terms of quick-sort but couldn't think of a solution which gives me better complexity than using standard sorting methods. Please help me find an algorithm which allows us to leverage the sorted sub-array property and result in better time complexity than running Quicksort on the input. This is the merge sort simulation I thought of, using this example: ``` 1) For position 0, Comparing 1 & 2, 1 is smaller let it stay at it's original place 2) For position 1, Comparing 2 & 4, 2 is smaller so swap 2 and 4 3) For position 2, Comparison now is between 4 and 3 (5 > 4 anyways) swap 3 and 5 4) For position 3, Comparison between 4 & 5, swap 4 and 7 5) For position 4, Comparison between 7 & 5, swap 8 and 5 6) For position 5, Comparison between 7 & 8 (OUCH!!) it should have been between 7 & 6 ``` It seems that this problem is similar to sorting sorted rows of a matrix, where in-place merge is too complicated.