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]

In article <11********************@o13g2000cwo.googlegroups.c om>,
kitts <la*********@gmail.com> wrote:

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.

--
"Never install telephone wiring during a lightning storm." -- Linksys

[Martin Ambuhl]

kitts wrote:

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.
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/2005
http://www.cpax.org.uk
email: rjh at above domain

[Ben Pfaff]

"kitts" <la*********@gmail.com> writes:

[ 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).
--
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}

[Christian Bau]

In article <11********************@o13g2000cwo.googlegroups.c om>,
"kitts" <la*********@gmail.com> wrote:

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]

kitts wrote:

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