Merge sort and quicksort
The sorts of lesson 47 split the work into two loops. Divide and conquer splits the array itself: sort two halves and combine them, or partition around a pivot and sort the parts. Both are recursive, and both are fast enough for real data.
Merge sort
Merge sort cuts the range in half until one element remains, then merges the sorted halves into a temporary array and copies them back. The merge is stable: when two values are equal, the one from the left half goes first. The work is O(n log n) and the extra array is O(n).
#include <stdio.h>
#include <stdlib.h>
static void merge(int *values, int *temporary, int low, int middle, int high)
{
int left = low;
int right = middle + 1;
int next = low;
while (left <= middle && right <= high) {
if (values[left] <= values[right]) {
temporary[next++] = values[left++];
} else {
temporary[next++] = values[right++];
}
}
while (left <= middle) {
temporary[next++] = values[left++];
}
while (right <= high) {
temporary[next++] = values[right++];
}
for (int i = low; i <= high; i++) {
values[i] = temporary[i];
}
}
static void sort(int *values, int *temporary, int low, int high)
{
if (low >= high) {
return;
}
int middle = low + (high - low) / 2;
sort(values, temporary, low, middle);
sort(values, temporary, middle + 1, high);
merge(values, temporary, low, middle, high);
}
int main(void)
{
int values[7] = {38, 27, 43, 3, 9, 82, 10};
int *temporary = malloc(7 * sizeof *temporary);
if (temporary == NULL) {
return 1;
}
sort(values, temporary, 0, 6);
for (int i = 0; i < 7; i++) {
printf("%d ", values[i]);
}
printf("\n");
free(temporary);
return 0;
}
gcc -Wall -Wextra merge.c -o merge
./merge
3 9 10 27 38 43 82
The middle is computed as low + (high - low) / 2 rather than (low + high) / 2, which cannot overflow. The temporary array is allocated once in main and passed down, so the recursion allocates nothing.
Quicksort
Quicksort chooses the last element as the pivot, moves every smaller value to the left of it, and puts the pivot between the two sides. The partition returns the pivot's final index, and the two halves are sorted in place. The extra memory is O(log n) for the recursion, not O(n).
#include <stdio.h>
static void swap(int *a, int *b)
{
int temporary = *a;
*a = *b;
*b = temporary;
}
static int partition(int *values, int low, int high)
{
int pivot = values[high];
int smaller = low;
for (int i = low; i < high; i++) {
if (values[i] < pivot) {
swap(&values[i], &values[smaller]);
smaller++;
}
}
swap(&values[smaller], &values[high]);
return smaller;
}
static void sort(int *values, int low, int high)
{
if (low < high) {
int pivot = partition(values, low, high);
sort(values, low, pivot - 1);
sort(values, pivot + 1, high);
}
}
int main(void)
{
int values[7] = {38, 27, 43, 3, 9, 82, 10};
sort(values, 0, 6);
for (int i = 0; i < 7; i++) {
printf("%d ", values[i]);
}
printf("\n");
return 0;
}
gcc -Wall -Wextra quick.c -o quick
./quick
3 9 10 27 38 43 82
The smaller index marks the boundary of the values below the pivot; every smaller element is swapped into that region. After the loop the pivot itself is swapped into the boundary, which is its final place. Quicksort is not stable, and the sorted-last pivot makes an already sorted array its worst case.
Merging two sorted arrays
The merge step is useful on its own. Two arrays that are already sorted are combined into one by repeatedly taking the smaller front element and then copying whatever remains. The loop is the same as the merge of the recursive sort, without the recursion around it.
#include <stdio.h>
int main(void)
{
int left[3] = {1, 3, 5};
int right[3] = {2, 4, 6};
int merged[6];
int i = 0;
int j = 0;
int next = 0;
while (i < 3 && j < 3) {
if (left[i] <= right[j]) {
merged[next++] = left[i++];
} else {
merged[next++] = right[j++];
}
}
while (i < 3) {
merged[next++] = left[i++];
}
while (j < 3) {
merged[next++] = right[j++];
}
for (int k = 0; k < 6; k++) {
printf("%d ", merged[k]);
}
printf("\n");
return 0;
}
gcc -Wall -Wextra mergetwo.c -o mergetwo
./mergetwo
1 2 3 4 5 6
The two trailing loops are not optional: when one array runs out, the rest of the other one is already in order and is copied as a block. Forgetting them loses the tail of the longer array, the mistake in the first half of the last section.
How many comparisons
A counter in the merge loop shows the logarithmic factor. Eight elements are merged in three levels, and each level compares at most seven times, so the total is close to n log n. The same counter on the quadratic sorts of lesson 47 would grow with the square of the count.
#include <stdio.h>
#include <stdlib.h>
static int comparisons = 0;
static void merge(int *values, int *temporary, int low, int middle, int high)
{
int left = low;
int right = middle + 1;
int next = low;
while (left <= middle && right <= high) {
comparisons++;
if (values[left] <= values[right]) {
temporary[next++] = values[left++];
} else {
temporary[next++] = values[right++];
}
}
while (left <= middle) {
temporary[next++] = values[left++];
}
while (right <= high) {
temporary[next++] = values[right++];
}
for (int i = low; i <= high; i++) {
values[i] = temporary[i];
}
}
static void sort(int *values, int *temporary, int low, int high)
{
if (low >= high) {
return;
}
int middle = low + (high - low) / 2;
sort(values, temporary, low, middle);
sort(values, temporary, middle + 1, high);
merge(values, temporary, low, middle, high);
}
int main(void)
{
int values[8] = {8, 3, 7, 4, 6, 1, 5, 2};
int *temporary = malloc(8 * sizeof *temporary);
if (temporary == NULL) {
return 1;
}
sort(values, temporary, 0, 7);
printf("comparisons: %d\n", comparisons);
free(temporary);
return 0;
}
gcc -Wall -Wextra counts.c -o counts
./counts
comparisons: 16
Sixteen is 2n for eight elements, well below the 28 comparisons the same input would need in the worst case of the elementary sorts. The number of levels is what grows slowly; doubling the input adds one level and one pass of merges.
No copy back, no shrink
The merge step writes into the temporary array, so the result must be copied back into the original range. A version that forgets the copy compiles, runs and prints the input unchanged, which is a quiet reminder that the recursion sorted a copy nobody reads:
#include <stdio.h>
#include <stdlib.h>
static void merge(int *values, int *temporary, int low, int middle, int high)
{
int left = low;
int right = middle + 1;
int next = low;
while (left <= middle && right <= high) {
if (values[left] <= values[right]) {
temporary[next++] = values[left++];
} else {
temporary[next++] = values[right++];
}
}
while (left <= middle) {
temporary[next++] = values[left++];
}
while (right <= high) {
temporary[next++] = values[right++];
}
}
static void sort(int *values, int *temporary, int low, int high)
{
if (low >= high) {
return;
}
int middle = low + (high - low) / 2;
sort(values, temporary, low, middle);
sort(values, temporary, middle + 1, high);
merge(values, temporary, low, middle, high);
}
int main(void)
{
int values[7] = {38, 27, 43, 3, 9, 82, 10};
int *temporary = malloc(7 * sizeof *temporary);
if (temporary == NULL) {
return 1;
}
sort(values, temporary, 0, 6);
for (int i = 0; i < 7; i++) {
printf("%d ", values[i]);
}
printf("\n");
free(temporary);
return 0;
}
gcc -Wall -Wextra notemp.c -o notemp
./notemp
38 27 43 3 9 82 10
The second mistake is the recursion bound. Calling sort(values, low, pivot) instead of sort(values, low, pivot - 1) can pass the same range down again when the pivot is the last element, and the recursion never shrinks until the stack ends:
#include <stdio.h>
static void swap(int *a, int *b)
{
int temporary = *a;
*a = *b;
*b = temporary;
}
static int partition(int *values, int low, int high)
{
int pivot = values[high];
int smaller = low;
for (int i = low; i < high; i++) {
if (values[i] < pivot) {
swap(&values[i], &values[smaller]);
smaller++;
}
}
swap(&values[smaller], &values[high]);
return smaller;
}
static void sort(int *values, int low, int high)
{
if (low < high) {
int pivot = partition(values, low, high);
sort(values, low, pivot);
sort(values, pivot + 1, high);
}
}
int main(void)
{
int values[5] = {5, 2, 9, 1, 6};
sort(values, 0, 4);
printf("%d\n", values[0]);
return 0;
}
gcc -Wall -Wextra recurse.c -o recurse
timeout 5 ./recurse; echo "exit: $?"
exit: 139
The pivot stays in the range, so the left recursion receives a range that still ends at the pivot and never gets smaller. The exit status 139 is the segmentation fault after the stack overflows; the fix is the pivot - 1 bound from the quicksort section.
Exercises
- Sort an array of strings with merge sort, using strcmp as the comparison.
- Choose the middle element as the pivot in quicksort and compare the comparison count with the last-element version on a sorted array.
- Merge three sorted arrays into one with a loop that picks the smallest of the three fronts.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What extra memory does merge sort need?
Answer
A temporary array as long as the input
The merge writes into a temporary array and copies the range back, so the extra space grows with the input.
-
Where does quicksort put the pivot after a partition?
Answer
At its final sorted position
All smaller values move to its left, the pivot swaps into the boundary, and the two sides are sorted independently.
-
Why does the merge step copy the rest of the longer half?
Answer
The remaining values are already in order
When one side runs out, the other side is sorted, so its tail is copied as a block into the result.
-
Why is the middle computed as
low + (high - low) / 2?Answer
So adding the two bounds cannot overflow
The subtraction keeps both operands small, while
(low + high) / 2can overflow near the top of the range. -
What does this program print?
#include <stdio.h> static void merge(int*v,int*t,int l,int m,int h){int a=l,b=m+1,n=l;while(a<=m&&b<=h)t[n++]=v[a]<=v[b]?v[a++]:v[b++];while(a<=m)t[n++]=v[a++];while(b<=h)t[n++]=v[b++];for(int i=l;i<=h;i++)v[i]=t[i];} static void sort(int*v,int*t,int l,int h){if(l>=h)return;int m=l+(h-l)/2;sort(v,t,l,m);sort(v,t,m+1,h);merge(v,t,l,m,h);} int main(void){int v[7]={38,27,43,3,9,82,10},t[7];sort(v,t,0,6);for(int i=0;i<7;i++)printf("%d ",v[i]);printf("\n");return 0;}Answer
3 9 10 27 38 43 82
The recursion sorts both halves and the final merge interleaves them into ascending order.
-
What does this program print?
#include <stdio.h> static void swap(int*a,int*b){int t=*a;*a=*b;*b=t;} static int part(int*v,int l,int h){int p=v[h],s=l;for(int i=l;i<h;i++)if(v[i]<p){swap(&v[i],&v[s]);s++;}swap(&v[s],&v[h]);return s;} static void sort(int*v,int l,int h){if(l<h){int p=part(v,l,h);sort(v,l,p-1);sort(v,p+1,h);}} int main(void){int v[7]={38,27,43,3,9,82,10};sort(v,0,6);for(int i=0;i<7;i++)printf("%d ",v[i]);printf("\n");return 0;}Answer
3 9 10 27 38 43 82
The partition puts every smaller value left of the pivot, and the recursion finishes the sorted order.
-
What does this program print for eight elements?
#include <stdio.h> static int c=0; static void merge(int*v,int*t,int l,int m,int h){int a=l,b=m+1,n=l;while(a<=m&&b<=h){c++;t[n++]=v[a]<=v[b]?v[a++]:v[b++];}while(a<=m)t[n++]=v[a++];while(b<=h)t[n++]=v[b++];for(int i=l;i<=h;i++)v[i]=t[i];} static void sort(int*v,int*t,int l,int h){if(l>=h)return;int m=l+(h-l)/2;sort(v,t,l,m);sort(v,t,m+1,h);merge(v,t,l,m,h);} int main(void){int v[8]={8,3,7,4,6,1,5,2},t[8];sort(v,t,0,7);printf("%d\n",c);return 0;}Answer
16
The three merge levels compare at most seven times each, and this input needs sixteen comparisons.
-
What does the version that forgets to copy back print?
Answer
38 27 43 3 9 82 10, the input order
The merge sorted only the temporary array, so the original range is unchanged when it is printed.
-
What happens with
sort(values, low, pivot)instead ofpivot - 1?Answer
The range stops shrinking and the stack overflows
The left recursion still includes the pivot, so it can receive the same range again until the stack ends with status 139.
-
What goes wrong if the merge skips the trailing copy loops?
Answer
The tail of the longer half is lost
After one side is exhausted, the other side still has elements that must be copied into the merged result.
The code on this page was run with gcc (Alpine 15.2.0) 15.2.0 on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev