how can i do this in o(n)

[kitts]

A given array of size 2n with n elements in sorted order. Another array
with size n & n elements in it in sorted order. Merge the two arrays &
final array should be in sorted order without using extra memory

 

[Walter Roberson]

A given array of size 2n with n elements in sorted order. Another array
with size n & n elements in it in sorted order. Merge the two arrays &
final array should be in sorted order without using extra memory

That sounds like an assignment question.

How does one know where the n elements are in the array of size 2n ?
The question as stated does -not- indicate that the n elements
are at the beginning of the array, nor that the n elements are
evenly distributed -- only that the elements are in order.

 

[Martin Ambuhl]

A given array of size 2n with n elements in sorted order. Another array
with size n & n elements in it in sorted order. Merge the two arrays &
final array should be in sorted order without using extra memory

Not today. Post your instructor's name and email address, and I'm sure
someone will be glad to send him an answer to your demand.

 

[Richard Heathfield]

(Subject line: "how can i do this in o(n)")

kitts said:

A given array of size 2n with n elements in sorted order. Another array
with size n & n elements in it in sorted order. Merge the two arrays &
final array should be in sorted order without using extra memory

Consider writing a C function to do it. Post your best-effort code if you
get stuck.Here's an algorithm hint, using playing cards (E means "empty
slot"):

A 5 6 9 E E E E

2 7 8 K

You can compare the last card in each deck, and move the highest value card
out of those two to the last empty slot in the upper deck. Then compare
whichever card "lost" the previous comparison to the last card in the other
deck that has not yet been shoved into all that lovely space at the back.

 

[Ben Pfaff]

[ Subject: how can i do this in o(n) ]

A given array of size 2n with n elements in sorted order. Another array
with size n & n elements in it in sorted order. Merge the two arrays &
final array should be in sorted order without using extra memory

I don't think this problem is solvable in o(n) time.
I think it should be solvable in O(n).

 

[Christian Bau]

A given array of size 2n with n elements in sorted order. Another array
with size n & n elements in it in sorted order. Merge the two arrays &
final array should be in sorted order without using extra memory

Not possible in o (n).
Trivial in O (n).

 

[August Karlstrom]

A given array of size 2n with n elements in sorted order. Another array
with size n & n elements in it in sorted order.

An array of n elements of which n elements are sorted... sounds like a
(fully) sorted array!?


August

 

[Alan Balmer]

An array of n elements of which n elements are sorted... sounds like a
(fully) sorted array!?

Yes. There is some question about the composition of the other array,
however.