From time to time it’s nice to take a break from the high-level, web-centric stuff we do and just try for the old CS classics. For example, here’s mergesort in C. Not guaranteed to be fool-proof, but a cursory run tells me it’s working. Leave comments if you have any corrections or tips.

The coolest thing about this is the way it finds the approximate midpoint in order to split the list into two. The loop in the mergesort function pits two pointers against each other, one twice as fast as the other (it moves ahead 2 nodes for every 1 the other does). When one reaches the end, the other is in the middle (roughly).


node *merge( node *a, node *b )
{
  if( a == NULL )
    return b;
  if( b == NULL )
    return a;
 
  node *res = NULL;
 
  if( a->data < b->data )
  {
    res = a;
    res->next = merge( a->next , b );
  }
  else
  {
    res = b;
    res->next = merge( a , b->next );
  }
  
  return res;
}
 
node *mergesort( node *head )
{
  if( head == NULL || head->next == NULL )
    return head;
 
  node *mid = head;
  node *end = head->next;
  
  while( end != NULL && end->next != NULL )
  {
    mid = mid->next;
    end = end->next->next;
  }
 
  end = mid;
  mid = mid->next;
  end->next = NULL;
 
  return merge( mergesort(head),mergesort(mid));
 
}