Advanced Programming I Lecture Notes

2 February 2006 • Faster Sorting

template <typename T>
void
merge(
  T * temp_left, T * const temp_right, 
  T * a_left, T * const a_mid , T * const a_right) {

  const unsigned len = (temp_right - temp_left);
  assert(len == ((a_right - a_mid) + (a_mid - a_left)));

  T * oam = a_mid;

  while (temp_left < temp_right)
    if ((a_left < a_mid) ∧ ((oam == a_right) or (*a_left < *oam)))
      *temp_left++ = *a_left++;
    else
      *temp_left++ = *oam++;

  memcpy(a_right - len, temp_right - len, sizeof(T)*len);
  }

This page last modified on 24 January 2006.