0

Possible Duplicates:
How to sort in-place using the merge sort algorithm?
Regarding in-place merge in an array

Given an array of size N, which is divided into two sets of sorted integers(0 to P and P+1 to N-1). How would you sort this array using constant extra space (O(1)) and in O(n) time. For e.g

A = {1,3,5,7,2,4,6,8}, here N = 8, P = 3 and elements from 0 to 3 are sorted and elements from 4 to 7 are sorted.

Desired O/P: A = {1,2,3,4,5,6,7,8}

Community
  • 1
  • 1
Ravi Gupta
  • 6,258
  • 17
  • 56
  • 79
  • "how to merge two sorted integer array in place using O(n) time and O(1) space cost" : http://stackoverflow.com/questions/2126219/how-to-merge-two-sorted-integer-array-in-place-using-on-time-and-o1-space-cos – Mark Byers Jul 22 '10 at 18:02
  • Would this be homework, perchance? – Stephen Jul 22 '10 at 18:04
  • Who on earth would ask this on a job interview?!? – Daniel Brückner Jul 22 '10 at 18:04
  • @Daniel Brückner Are you surprised at it because you think it is easy or hard? – Stephen Jul 22 '10 at 21:44
  • Because it is hard. I guess the only people that would ask such questions are people not knowing the (correct) answer with the possible exception that you are looking for a job in the field of search algorithm research. – Daniel Brückner Jul 23 '10 at 09:12

2 Answers2

0

Your input array doesn't need to be sorted. You simply write out the numbers 0..N-1 (or 1..N your example is a bit confusing). I think you must have mis-stated your problem.

High Performance Mark
  • 77,191
  • 7
  • 105
  • 161
  • I'm guessing using the numbers 1-8 was just a toy example. He could have used any range of 8-unique numbers, like {1, 20, 21, 2, 3, 7, 50, 100}. This should yield the merged array {1, 2, 3, 7, 20, 21, 50, 100}. – efritz Dec 08 '12 at 23:20
0

If I understand you correctly, you can allocate a new array to hold the result. So what you're doing is merging two sorted lists. A simple two-way merge does that nicely.

Jim Mischel
  • 131,090
  • 20
  • 188
  • 351
  • Allocating a new array to hold the result is an O(n) extra space operation which is disallowed by his constraints. – Mark Byers Jul 22 '10 at 18:05
  • `O(1)` space does not allow allocating a new array. All (known) solutions to this problem are freaking complex compared to the simplicity of the problem without the `O(1)` space constraint. – Daniel Brückner Jul 22 '10 at 18:07
  • 1
    I was confused by his wording. He said "O(1) extra space." The "extra" led me to believe that he could allocate a new array. – Jim Mischel Jul 25 '10 at 22:12