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);
}```