Merge sort in C

Split, sort each half, then merge the two sorted runs.

static void merge(int *values, int *scratch, int low, int mid, int high) {
    int i = low;
    int j = mid + 1;
    int k = low;

    while (i <= mid && j <= high) {
        scratch[k++] = (values[i] <= values[j]) ? values[i++] : values[j++];
    }
    while (i <= mid) {
        scratch[k++] = values[i++];
    }
    while (j <= high) {
        scratch[k++] = values[j++];
    }
    for (int x = low; x <= high; x++) {
        values[x] = scratch[x];
    }
}

void mergesort(int *values, int *scratch, int low, int high) {
    if (low >= high) {
        return;
    }
    int mid = low + (high - low) / 2;
    mergesort(values, scratch, low, mid);
    mergesort(values, scratch, mid + 1, high);
    merge(values, scratch, low, mid, high);
}

How it works

1. Merging needs scratch space the size of the range.
2. It is stable, which quicksort is not.
3. The recursion depth is logarithmic, the work per level linear.

Keywords and builtins used here

• for
• if
• int
• merge
• mergesort
• return
• static
• void
• while

The run, in numbers

Lines

28

Characters to type

634

Tokens

243

Three-star pace

95 tpm

At the three-star pace of 95 tokens a minute, this run takes about 153 seconds.

Type this snippet

Step 5 of 5 in Sorting & searching, step 5 of 20 in Data structures & algorithms.

← Previous Next →