Merging two arrays

Given two sorted integer arrays and the larger array has room for the second. Merge the smaller array into the larger one, in O(n) time and O(1) space.

Answer:

l_begin l_end free
| | |
[4][6][8][10][22][ ][ ][ ][ ]

sml_begin small_end
| |
[1][2][3][20]

void InplaceMerge(int * l_up, int * l_down, int* s_up, int* s_down)
{
int* free = l_down + (s_down-s_up);
while(s_end <= s_begin)
{
while(*l_end >= *s_end)
{
*free = *l_end;
--free; --l_end;
}
while (*s_end >= *l_end)
{
*free = *s_end;
--free; --s_end;
}
}
}

No comments: