CodeUtility
Making your developer's life easier!
C/C++ Algorithms

Merge Sort

Use divide and conquer for predictable O(n log n) sorting.

What is Merge Sort?

Merge sort recursively sorts halves and combines them into an ordered range.

Important points

  • Test empty, single-element, duplicate, and already sorted inputs.
  • Separate correctness from optimization.
  • Use the standard library in production unless a custom implementation is justified.

Merge Sort visualizer

O(n)

Use Play or Step to follow each comparison and data movement.

C and C++ code examples

C
Run code →
main.c
#include <stdio.h>
#include <stdlib.h>

void merge_sort(int *values, int *temporary, int left, int right) {
    if (right - left < 2) return;
    int middle = (left + right) / 2;
    merge_sort(values, temporary, left, middle);
    merge_sort(values, temporary, middle, right);

    int first = left;
    int second = middle;
    int output = left;
    while (first < middle && second < right) {
        temporary[output++] = values[first] < values[second]
            ? values[first++] : values[second++];
    }
    while (first < middle) temporary[output++] = values[first++];
    while (second < right) temporary[output++] = values[second++];
    for (int index = left; index < right; ++index) {
        values[index] = temporary[index];
    }
}

int main(void) {
    int values[] = {8, 3, 6, 2, 7};
    int temporary[5];
    merge_sort(values, temporary, 0, 5);
    for (int index = 0; index < 5; ++index) {
        printf("%d ", values[index]);
    }
}
Result of running the code
2 3 6 7 8
C++
Run code →
main.cpp
#include <algorithm>
#include <iostream>
#include <vector>

void merge_sort(std::vector<int>& values) {
    if (values.size() < 2) return;
    auto middle = values.begin() + values.size() / 2;
    std::vector<int> left(values.begin(), middle);
    std::vector<int> right(middle, values.end());
    merge_sort(left);
    merge_sort(right);
    std::merge(left.begin(), left.end(), right.begin(), right.end(),
               values.begin());
}

int main() {
    std::vector values{8, 3, 6, 2, 7};
    merge_sort(values);
    for (int value : values) {
        std::cout << value << ' ';
    }
}
Result of running the code
2 3 6 7 8

C and C++ comparison

Both versions require O(n) auxiliary storage. C manages one temporary buffer explicitly; C++ uses standard algorithms and vectors for clearer ownership.

C

Loops, pointers, lengths, and temporary buffers are written explicitly.

C++

Iterators and standard algorithms separate operations from container representation.

Practice exercises

Run both versions, then modify them to observe the different language guarantees.

  • Trace each comparison on paper.
  • Test duplicates and extreme values.
  • Benchmark the custom implementation against the standard library.

Practice with a challenge

Use what this lesson covers to solve a real problem. Each challenge runs in your browser with instant tests and an AI review.

All challenges