Sorted List Array Question

Question

Is it possible that two sorted list of size n/2 each can be merged using n/2 size of working ?array???

Answer 1

That has not impact on complexity O(n). You can not get n/2 all the time. A= [1,2,3,10] B= [4,5,6,8]

You need n-1 for that.

Answer 2

If you mean working array as in the extra storage required over and above the final array, you don't even need that. To sort two lists which are already sorted, you only need to merge them and that requires only two values (one per source list) rather than n/2.

The algorithm is as follows:

create empty list newlist
set idx1 to start of list1
set idx2 to start of list2
while idx1 within list1 or idx2 within list2:
    if idx1 beyond list1:
        append list2[idx2] to newlist
        increment idx2
    else if idx2 beyond list2:
        append list1[idx1] to newlist
        increment idx1
    else if list1[idx1] is less than list2[idx2]:
        append list1[idx1] to newlist
        increment idx1
    else:
        append list2[idx2] to newlist
        increment idx2

If you mean "Can you combine two n/2-size arrays into another n/2-size array?" then, short of doing some trickery where you can combine two elements into one (such as tow 16-bit integers into a 32-bit element), no, it's not possible.