Data-structures

Mergesort and Quicksort

Mergesort (not an in-place sort for arrays)

mergesort(a, i, j)
{
   if (i >= j) return;
   mid = (i + j)/2;
   mergesort(a, i, mid);
   mergesort(a, mid + 1, j);
   merge(a, i, j);
}
merge(a, i, j)
{
   start = i;
   mid = (i + j)/2;
   k = mid + 1;
   l = i;
   while (i <= mid && k <= j) {
      if (a[i] <= a[k]) {
         b[l++] = a[i++];
      } else {
         b[l++] = a[k++];
      }
   }
   if (i > mid) {
      for (; k <= j;) b[l++] = a[k++];
   } else {   
      // k > j
      for (; i <= mid;) b[l++] = a[i++];
   }
   // copy back b to a
   // Note here the usage of temporary array b
   for (l = start; l <= j; l++) {
      a[l] = b[l];
   }
}

Quicksort (an in-place sort)

quicksort(a, i, j)
{
   if (i >= j) return;
   pindex = random number between i and j;
   pivot = a[pindex];
   // swap pivot and a[j]
   a[pindex] = a[j];
   a[j] = p;
   m = i – 1; // m sandwiches the array from the left
   n = j; // n sandwiches the array from the right
   do {
      do { m++; } while (a[m] < pivot);
      do { n--; } while (a[n] > pivot && n > i);
      if (m < n) {
         // swap a[m] and a[n];
      }
   } while (m < n);
   // m >= n and therefore a[m] must be greater than pivot.
   // hence it is fine to now swap with the pivot in a[j]
   a[j] = a[m];
   // put the pivot in the middle
   a[m] = pivot;
   quicksort(a, i, m-1);
   quicksort(a, m+1, j);
}