Understanding merge sort optimization: avoiding copies

Question

I have below merge sort program in algorithms book, it is mentioned that The main problem is that merging two sorted lists requires linear extra memory, and the additional work spent copying to the temporary array and back, throughout the algorithm, has the effect of slowing down the sort considerably. This copying can be avoided by judiciously switching the roles of "a" and "tmp_array" at alternate levels of the recursion.

My question is what does author mean "copying can be avoided by judiciously switching the roles of a and tmp_array at alternate levels of the recursion" and how it is possible in following code? Request to show an example how we can achieve this?

void mergesort( input_type a[], unsigned int n ) {

    input_type *tmp_array;
    tmp_array = (input_type *) malloc( (n+1) * sizeof (input_type) );
    m_sort( a, tmp_array, 1, n );
    free( tmp_array );
}

void m_sort( input_type a[], input_type tmp_array[ ], int left, int right ) {

    int center;
    if( left < right ) {

    center = (left + right) / 2;
    m_sort( a, tmp_array, left, center );
    m_sort( a, tmp_array, center+1, right );
    merge( a, tmp_array, left, center+1, right );
    }
}

void merge( input_type a[ ], input_type tmp_array[ ], int l_pos, int r_pos, int right_end ) {

    int i, left_end, num_elements, tmp_pos;
    left_end = r_pos - 1;
    tmp_pos = l_pos;
    num_elements = right_end - l_pos + 1;

    /* main loop */

    while( ( 1_pos <= left_end ) && ( r_pos <= right_end ) )

        if( a[1_pos] <= a[r_pos] )
            tmp_array[tmp_pos++] = a[l_pos++];
        else
            tmp_array[tmp_pos++] = a[r_pos++];

    while( l_pos <= left_end )  /* copy rest of first half */
        tmp_array[tmp_pos++] = a[l_pos++];

    while( r_pos <= right_end ) /* copy rest of second half */
        tmp_array[tmp_pos++] = a[r_pos++];

    /* copy tmp_array back */
    for(i=1; i <= num_elements; i++, right_end-- )
        a[right_end] = tmp_array[right_end];

}

Answer 1

I'm going to assume that, without looking at this code, it is performing merge sort by declaring a contiguous block of memory the same size as the original.

So normally merge sort is like this:

• split array in half
• sort half-arrays by recursively invoking MergeSort on them
• merge half-arrays back

I'm assuming it's recursive, so no copies will be done before we're sorting sub-arrays of size 2. Now what happens?

_ means it is memory we have available, but we don't care about the data in it

original:
   8    5    2    3      1    7    4    6
   _    _    _    _      _    _    _    _

Begin recursive calls:

recursive call 1:
  (8    5    2    3)    (1    7    4    6)
   _    _    _    _      _    _    _    _

recursive call 2:
 ((8    5)  (2    3))  ((1    7)  (4    6))
   _    _    _    _      _    _    _    _

recursive call 3:
(((8)  (5))((2)  (3)))(((1)  (7))((4)  (6)))
   _    _    _    _      _    _    _    _

Recursive calls resolving with merging, PLUS COPYING (uses more memory, or alternatively is 'slower'):

merge for call 3, using temp space:
(((8)  (5))((2)  (3)))(((1)  (7))((4)  (6)))    --\ perform merge
(( 5    8 )( 2    3 ))(( 1    7 )( 4    6 ))   <--/ operation

UNNECESSARY: copy back:
(( 5    8 )( 2    3 ))(( 1    7 )( 4    6 ))   <--\ copy and
   _    _    _    _      _    _    _    _       --/ ignore old

merge for call 2, using temp space:
(( 5    8 )( 2    3 ))(( 1    7 )( 4    6 ))    --\ perform merge
(  2    3    5    8  )(  1    4    6    7  )   <--/ operation

UNNECESSARY: copy back:
(  2    3    5    8  )(  1    4    6    7  )   <--\ copy and
   _    _    _    _      _    _    _    _       --/ ignore old

merge for call 1, using temp space:
(  2    3    5    8  )(  1    4    6    7  )    --\ perform merge
   1    2    3    4      5    6    7    8      <--/ operation

UNNECESSARY: copy back:
   1    2    3    4      5    6    7    8      <--\ copy and
   _    _    _    _      _    _    _    _       --/ ignore old

What the author is suggesting Recursive calls resolving with merging, WITHOUT COPYING (uses less memory):

merge for call 3, using temp space:
(((8)  (5))((2)  (3)))(((1)  (7))((4)  (6)))    --\ perform merge
(( 5    8 )( 2    3 ))(( 1    7 )( 4    6 ))   <--/ operation

merge for call 2, using old array as temp space:
(  2    3    5    8  )(  1    4    6    7  )   <--\ perform merge
(( 5    8 )( 2    3 ))(( 1    7 )( 4    6 ))    --/ operation (backwards)

merge for call 1, using temp space:
(  2    3    5    8  )(  1    4    6    7  )    --\ perform merge
   1    2    3    4      5    6    7    8      <--/ operation

There you go: you don't need to do copies as long as you perform each "level" of the merge-sort tree in lock-step, as shown above.

You may have a minor issue of parity, also as demonstrated above. That is, your result may be in your temp_array. You either have three options for dealing with this:

• returning the temp_array as the answer, and release the old memory (if your application is fine with that)
• perform a single array copy operation, to copy temp_array back into your original array
• allow yourself to consume a mere twice-as-much memory, and perform a single cycle of merges from temp_array1 to temp_array2 then back to original_array, then release temp_array2. The parity issue should be resolved.

---

This is not necessarily "faster":

additional work spent copying to the temporary array and back

This is actually not the core reason why it's 'faster' per se. It is obviously not asymptotically faster, nor necessarily even faster. There is a notion of latency vs. throughput. Generally running time is measured in latency, because extra garbage work (like releasing memory) may be done asynchronously. You don't necessarily need to copy "back" to the original array depending on your language. However, if you are repeating something many times on memory-bound hardware in a garbage-collected language, the garbage collection can occasionally be forced to spike if the GC algorithm is a poor choice for what you are doing (or if this is C, maybe you are waiting to allocate). Thus if you were to create extra memory in a GC language, it should not really count against you. Granted, this may cause you not to take advantage of cache properly if you use too much memory. You'd have to benchmark it yourself, very carefully for your use case.

I do not recommend creating random temporary arrays for each step though, as that would make memory O(N log(N)) and this is a trivial optimization.

---

Minor notes on in-placeness:

Also, the reason you can't naively do it in-place is because while you are merging two sorted sub-arrays, the new result sorted sub-array may take arbitrarily many from one input array before spontaneously swap to the other array. For example, as you can see we need a buffer because our input arrays might get split into fragments:

( 4  6  7  8 10)(1  2  3  5  9  11)(... other sub-arrays)
( 1)(6  7  8 10)(4)(2  3  5  9  11)(...
( 1  2)(7  8 10)(4  6)(3  5  9  11) ...
( 1  2  3)(8 10)(4  6  7)(5  9  11)
( 1  2  3  4(10)(8)(6  7)(5  9  11) ooph :-(
( 1  2  3  4  5)(8)(6  7)(10)(9 11) ooph

You might be able to so cleverly in-place if you do some weird variant of the kth-statistic median-of-medians algorithm, performing your merge into the middle of the two arrays rather than the start (merging from a specifically chosen element outwards left/decreasing and right/increasing simultaneously). I'm not sure how one would implement that though, or if the hunch is true.

(very minor note: Perhaps those who are familiar with sorting algorithms should be careful of comparing a traditional swap traditional swap operation involving a tmp variable in a register, which is two reads-from-cache and two writes-to-cache, to not-in-place copying to other bits of memory, without a per-operation counting argument.)

Certainly, OP's method is extremely simple to code for only twice as much memory.