Mergesort and Quicksort

Mergesort (not an in-place sort)

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
     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 starts from the left
      n = j; // n starts 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); // till m and n cross each other
      // 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);
}

 

This entry was posted in Data-structures. Bookmark the permalink.

Comments are closed.