gistfile1.h

void mergesort_(id* objs, size_t count, SEL cmp)
{
  // Base case.
  if (count < 2) return;
  
  size_t left_count = count / 2;
  size_t right_count = count – left_count;
  id left_objs[left_count];
  id right_objs[right_count];
  // Function pointer for comparison IMP.
  compare_IMP_ cmp_IMP = (compare_IMP_)[*objs methodForSelector:cmp];
  
  // Divide and conquer.
  memcpy(left_objs, objs, sizeof(id) * left_count);
  memcpy(right_objs, &objs[left_count], sizeof(id) * right_count);
  mergesort_(left_objs, left_count, cmp);
  mergesort_(right_objs, right_count, cmp);
  
  size_t cur_left = 0;
  size_t cur_right = 0;
  while (cur_left < left_count || cur_right < right_count)
  {
    id left = left_objs[cur_left];
    id right = right_objs[cur_right];
    
    // Special case where right side has element(s) remaining after
    // all left-side elements have been merged.
    if (cur_left == left_count) {
      objs[cur_left+cur_right] = right;
      cur_right++;
    }
    // Special case where left side has element(s) remaining after
    // all right-side elements have been merged.
    else if (cur_right == right_count) {
      objs[cur_left+cur_right] = left;
      cur_left++;
    }
    // Normal merge case: left > right
    else if (cmp_IMP(left, cmp, right) == NSOrderedDescending) {
      objs[cur_left+cur_right] = right;
      cur_right++;
    // Normal merge case: left <= right
    } else {
      objs[cur_left+cur_right] = left;
      cur_left++;
    }
  }
}