Cи. Сортировка методом слияния

Алгоритм сортировки слиянием заключается в рекурсивном делении массива пополам до массивов размером в один элемент (такой массив очевидно упорядочен) с последующим слиянием 2-х упорядоченных массивов. Алгоритм обеспечивает устойчивую (stable) сортировку.
(конечно, в данном примере сортируются целые числа, которые неотличимы друг от друга, однако, в ряде задач, когда сортируются структуры по некоторому ключу, устойчивость может быть необходима)

Этот алгоритм имеет сложность O(N log N) и требует дополнительную память на фазе слияния для получения отсортированного результата. Обычно в реализациях слияния требуется память того же размера, что и исходный массив, но тут рассмотрен вариант, когда достаточно дополнительной памяти размером с половину исходного массива.

Мы можем сократить память в два раза, поскольку в процессе сортировки получаем сливаемые массивы одинакового (второй может быть на один элемент длиннее) размера, которые расположены рядом, а результат слияния замещает их данные. Поэтому можно скопировать первый массив во вспомогательную память и начать размещать отсорированный результат поверх элементов первого. К тому моменту, когда данные результата достигнут второго массива, его начальные элементы уже будут скопированы в область результата.

На практике имеет смысл остановиться в разбиении массива при достижении резмера в несколько десятков элементов и сортировать такие массивы какой-нибудь простой квадратичной сортировкой (например, вставками). Дело тут в том, что накладные расходы на каждый шаг в рекурсивном разделении и последующем слиянии превышают подобные накладные расходы в простой сортировке.

Вот пример кода, реализующего такую сортировку для массива целых чисел.

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>

#define MSORT_LIM 20   // при таком размере массива выполняем сортировку подмассива вставками


// сортировка вставками, 
// используется для коротких подмассивов, получающихся при разбиении исходного
void
i_sort (int *a, int n)
{
  for (int i = 1; i < n; i++) {
    int t = a[i],
      j;
    for (j = i - 1; j >= 0 && t < a[j]; j--)
      a[j + 1] = a[j];
    a[j + 1] = t;
  }
}

// основная функция сортировки слиянием
// рекурсивно делит пополам исходный массив на 2 подмассива
// производит отсортированный массив путем слияния уже отсортированных подмассивов
// `t[]` вспомогательный массив достаточного размера для хранения самого длинного подмасива 
void
i_merge_srt (int *a, int n, int *t)
{
  if (n < MSORT_LIM) {
    i_sort(a, n);
    return;
  }

  // делим масссив пополам и рекурсивно сортируем половинки
  int mid = n / 2;
  i_merge_srt(a, mid, t);
  i_merge_srt(a + mid, n - mid, t);

  // Далее код слияния 2-х отсортированных половин в один сортированный массив

  // копируем первый подмассив во вспомогательную память, 
  // использую системную (обычно весьма быструю) функцию копирования
  memcpy(t, a, mid  * sizeof(*a));

  // копируем элементы 2-х подмассивов в область результата (начинающуюся поверх первого подмассива)
  // в порядке их возрастания (получаем отсортированную последовательность)
  int k = 0, i, j;  
  for (i = 0, j = mid; i < mid && j < n; k++)
    if (t[i] <= a[j])   // условие `<=` обеспечивает устойчивость сортировки
      a[k] = t[i++];
    else
      a[k] = a[j++];

  // скопируем "хвост" первого подмассива в результат
  memcpy(a + k, t + i, (mid - i) * sizeof(*a));
}

// функция-обертка над i_merge_srt(), обеспечивающая вспомогательную память достаточного размера
// возвращает 1 при успехе, 0 при невозможности выделить память
int
merge_srt (int *a, int n)
{
  if (n < 2)
    return 1;  // такой массив уже упорядочен

  int *tmp = malloc((n / 2) * sizeof(*a));
  if (!tmp)
    return 0;
  
  i_merge_srt(a, n, tmp);
  free(tmp);

  return 1;
}