algorithm - abstract inplace mergesort for effective merge sort -

i reading merge sort in algorithms in c++ robert sedgewick , have following questions.

static void mergeab(item[] c, int cl, item[] a, int al, int ar, item[] b, int bl, int br ) {      int = al, j = bl;     (int k = cl; k < cl+ar-al+br-bl+1; k++)     {         if (i > ar) { c[k] = b[j++]; continue; }         if (j > br) { c[k] = a[i++]; continue; }         c[k] = less(a[i], b[j]) ? a[i++] : b[j++];     } } 

the characteristic of basic merge worthy of note inner loop includes 2 tests determine whether ends of 2 input arrays have been reached. of course, these 2 tests fail, , situation cries out use of sentinel keys allow tests removed. is, if elements key value larger of other keys added ends of , aux arrays, tests can removed, because when (b) array exhausted, sentinel causes next elements c array taken b (a) array until merge complete.

however, not easy use sentinels, either because might not easy know largest key value or because space might not available conveniently.

for merging, there simple remedy. method based on following idea: given resigned copying arrays implement in-place abstraction, put second array in reverse order when copied (at no cost), associated index moves right left. arrangement leads largest element—in whichever array is—serving sentinel other array.

my questions on above text

1. what statement "when (b) array exhausted"? 'a (b)' here?

2. why author mentioning not easy determine largest key , how space related in determining largest key?

3. what author mean "given resigned copying arrays"? resigned in context?

4. request simple example in understanding idea mentioned simple remedy?

1. "when (b) array exhausted" shorthand "when either a array or b array exhausted".

2. the interface dealing sub-arrays of bigger array, can't go writing beyond ends of arrays.

3. the code copies data 2 arrays 1 other array. since copy inevitable, 'resigned copying arrays' means reluctantly accept inevitable arrays must copied.

4. tricky...that's going take time work out meant.

tangentially: that's not way i'd write loop. i'd inclined use:

int = al, j = bl; (int k = cl; <= ar && j <= br; k++) {     if (a[i] < b[j])         c[k] = a[i++];     else         c[k] = b[j++]; } while (i <= ar)     c[k++] = a[i++]; while (j <= br)     c[k++] = b[j++]; 

one of 2 trailing loops nothing. revised main merge loop has 3 tests per iteration versus 4 tests per iteration 1 original algorithm. i've not formally measured it, simpler merge loop quicker original single-loop algorithm.

the first 3 questions best suited english language learners.