Я написал сортировку слиянием на C и хотел бы получить совет, как ее улучшить. Любой совет поможет сделать код лучше!

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

static void mergesort_helper(void *array, uint32_t index, uint32_t length, size_t size_element, int32_t compare(void *, void *), void *storage)
{
   uint32_t i, j, k;
   if(length == 1)
   {
      /*printf("n%d, %dn", index, length);*/
      return;
   }

   mergesort_helper(array, index, length / 2, size_element, compare, storage);

   if(length % 2 == 0)
      mergesort_helper(array, (index + (index + length)) / 2, length / 2, size_element, compare, storage);
   else
      mergesort_helper(array, (index + (index + length)) / 2, length / 2 + 1, size_element, compare, storage);

   /*sorting part*/
   i = index;
   j = (index + (index + length)) / 2;
   k = 0;
   while(i < (index + (index + length)) / 2 || j < (index + length))
   {
      if(i < (index + (index + length)) / 2 && (compare(array + i * size_element, array + j * size_element) <= 0 || j >= (index + length)))
      {
          memcpy(storage + k * size_element, array + i * size_element, size_element);
          i++;
      }
      else if(j < (index + length) && (compare(array + i * size_element, array + j * size_element) > 0) || i >= (index + (index + length)) / 2)
      {
          memcpy(storage + k * size_element, array + j * size_element, size_element);
          j++;
      }
      k++;
   }
   memcpy(array + index * size_element, storage, length * size_element);
}

/*
   array -  to be sorted
   length - exclusive
   size_element - how big is one element
*/
void mergesort(void *array, uint32_t length, size_t size_element, int32_t compare(void *, void *))
{
   void *storage;
   if(length == 0)
      return;

   storage = malloc(size_element * length);
   mergesort_helper(array, 0, length, size_element, compare, storage);
   free(storage);
}


/*user code*/
int32_t compare(void *ptr1, void *ptr2)
{
   int32_t *temp_ptr1, *temp_ptr2;
   temp_ptr1 = (int32_t *)ptr1;
   temp_ptr2 = (int32_t *)ptr2;

   if(*temp_ptr1 < *temp_ptr2)
      return -1;
   else if(*temp_ptr1 > *temp_ptr2)
      return 1;

   return 0;
}

int main(void)
{
   uint32_t i;
   int32_t array[] = {6, 4, 3, 2, 7, -100, 1, 0, 5, 8, -100, 8};

   for(i = 0; i < sizeof(array) / sizeof(array[0]); i++)
   {
      printf("%d ", array[i]);
   }
   printf("n");

   mergesort(array, sizeof(array) / sizeof(array[0]), sizeof(array[0]), &compare);

   for(i = 0; i < sizeof(array) / sizeof(array[0]); i++)
   {
      printf("%d ", array[i]);
   }
   printf("n");
   return 0;
}

Избегайте дублирования кода

Ваш код более подробный, чем необходимо, потому что вы повторяете много вещей без необходимости или пишете вещи более сложным образом, чем необходимо. Например:

(index + (index + length)) / 2

Это выглядит очень странно и фактически эквивалентно:

index + length / 2

Что имеет гораздо больше смысла. Даже с этим изменением это выражение часто используется в коде, поэтому лучше дать ему имя:

uint32_t middle = index + length / 2;

Вы также продублировали звонок mergesort_helper() для обработки нечетных и четных случаев length. Однако вам не нужно, если вы напишете это так:

uint32_t middle = index + length / 2;
uint32_t end = index + length;

mergesort_helper(array, index, middle - index, size_element, compare, storage);
mergesort_helper(array, middle, end - middle, size_element, compare, storage);

Вы также можете рассмотреть возможность переименования index к start.

Использовать const для аргументов указателя в compare()

Поскольку функция compare() не должен изменять сравниваемые элементы, аргументы должны быть указателями на const:

int32_t compare(const void *ptr1, const void *ptr2) {
   const int32_t *temp_ptr1 = ptr1;
   const int32_t *temp_ptr2 = ptr2;
   ...
}

Оптимизация while-петля

Есть несколько незначительных изменений, которые можно сделать, чтобы ускорить while-петля немного. Во-первых, позвонив compare() вероятно, будет самой дорогой операцией, поэтому по возможности не вызывайте ее. Измените порядок, в котором вы проверяете вещи, чтобы использовать короткое замыкание:

if(i < middle && (j >= end || compare(...)))

В приведенном выше описании compare() будет вызываться только если i < middle является true а также j >= end является false.

Другая возможная оптимизация заключается в понимании того, что если i >= middle || j >= end, вы знаете, что вам нужно скопировать только оставшуюся часть одной стороны средней точки. Вместо того, чтобы делать это поэлементно, вы можете сделать это одним большим memcpy(). Это также упрощает if-Заявления в while-loop, вот так:

while (i < middle && j < end) {
    if (compare(array + i * size_element, array + j * size_element) <= 0) {
        memcpy(storage + k * size_element, array + i * size_element, size_element);
        i++;
    } else {
        memcpy(storage + k * size_element, array + j * size_element, size_element);
        j++;
    }

    k++;
}

/* Copy the remainder */
if (i < middle) {
    memcpy(storage + k * size_element, array + i * size_element, size_element * (middle - i));
} else {
    memcpy(storage + k * size_element, array + j * size_element, size_element * (end - j));
}

Вышеупомянутое также имеет то преимущество, что compare() вызывается только один раз на каждой итерации, тогда как в исходном коде его можно было вызвать дважды.

Избегать void арифметика указателя

Lau G упомянул указатели void и действительно сделал арифметика по void указатели незаконны. Простой обходной путь — привести его к char * первый:

static void mergesort_helper(void *array_ptr, ...)
{
    char *array = array_ptr;
    ...

Чтобы отловить такого рода проблемы, включите строгие предупреждения компилятора. Для GCC и Clang используйте -Wall -pedantic. Исправьте все предупреждения, которые выдает компилятор.

Интерфейс

Более подходящий тип для length было бы size_t. И я ожидал compare аргумент, чтобы быть функцией, возвращающей простой int, и принимая указатели на const void.

Программа испытаний

Программа испытаний может быть улучшена добавлением is_sorted() функция, чтобы подтвердить результат и вернуть соответствующее значение успеха / неудачи. Я бы порекомендовал сохранить повторный расчет длины массива в переменную:

const size_t length = sizeof array / sizeof array[0];

Предлагаю сократить объем i только петли:

for (size_t i = 0;  i < length;  ++i)

Компаратор

Нам не нужно объявлять и назначать отдельно, и нам не нужно писать приведение для преобразования из void*:

   int32_t *temp_ptr1, *temp_ptr2;
   temp_ptr1 = (int32_t *)ptr1;
   temp_ptr2 = (int32_t *)ptr2;

Я бы написал это как:

   int32_t const *a = ptr1;
   int32_t const *b = ptr2;

Я взял на себя смелость использовать более короткие и четкие имена, которые легче различить, где они используются.

Есть хорошо известный прием для возврата -1, 0 или +1 из сравнений, основанный на том факте, что логические значения равны 0 и 1:

   return (*a > *b) - (*a < *b);

Вспомогательная функция

Опять же, уменьшите объем переменных и объявите их там, где они назначены, чтобы уменьшить вероятность использования неинициализированных значений.

У нас есть повторный расчет (index + (index + length)) / 2. Этому можно не только дать имя, но и удалить ошибку, вызванную тем, что сумма достаточно велика, чтобы ее можно было переполнить:

const size_t mid_index = index + length / 2;

У нас много недействительных арифметических действий с указателями, например array + i * size_element. Так как array является указателем на void, сложение не определено — мы, вероятно, хотим изменить тип аргумента на char*. По аналогии, storage также должно быть char*.

Функция сортировки

Мы выделяем память, но вслепую продолжаем, когда malloc() возвращает нулевой указатель, ведущий к неопределенному поведению. Не делай этого!

Я не слишком уверен в своих знаниях о (недействительных) указателях, поэтому я не буду давать отзывы о материалах, связанных с указателями.

Ненужный оператор if … else.

if(length % 2 == 0)
    mergesort_helper(array, (index + (index + length)) / 2, length / 2, size_element, compare, storage);
else
    mergesort_helper(array, (index + (index + length)) / 2, length / 2 + 1, size_element, compare, storage);

Может быть превращен в:

mergesort_helper(array, (index + (index + length)) / 2, length / 2 + (length % 2), size_element, compare, storage);

Незначительное улучшение проверки длины mergesort.

Если массив имеет длину 1, можно также вернуться раньше, потому что массив длиной 1 уже отсортирован.

void mergesort(void *array, const uint32_t length, const size_t size_element, int32_t compare(void *, void *))
{
    ...
    if (length <= 1) { return; }
    ...
}

Используйте const

length а также size_element не меняйся в mergesort а также mergesort_helper функции. Это также относится к index в mergesort_helper функция. Лучше всего использовать ключевое слово const для обозначения этого, это также может быть полезно для компилятора.

void mergesort(void *array, const uint32_t length, const size_t size_element, int32_t compare(int32_t *, int32_t *))
static void mergesort_helper(void *array, const uint32_t index, const uint32_t length, const size_t size_element, int32_t compare(int32_t *, int32_t *), void *storage)

Стиль и удобочитаемость

Некоторые из них самоуверенны, поэтому вы можете использовать то, что считаете нужным.

• Используйте отступ в 4 пробела вместо 3.
• Используйте пробел между if/while/for а также (
• Используйте скобки в операторах if … else, даже если они состоят из одной строки. Возможно, позже в оператор if … else будет добавлено больше строк. Если в этом случае упустить скобки, это может привести к ошибкам, которых можно было бы избежать, если бы скобки были добавлены с самого начала.
• Сортировка слиянием состоит из двух слов, поэтому merge_sort было бы более уместно.
• (index + (index + length)) / 2 представляет средний индекс, который упростил бы чтение кода, если бы он был назначен константной переменной.

static void mergesort_helper(void *array, const uint32_t index, const uint32_t length, const size_t size_element, int32_t compare(void *, void *), void *storage)
{
    uint32_t i, j, k;
    if (length == 1)
    {
        /*printf("n%d, %dn", index, length);*/
        return;
    }

    const uint32_t m_index = (index + (index + length)) / 2;

    mergesort_helper(array, index, length / 2, size_element, compare, storage);

    mergesort_helper(array, m_index, length / 2 + length % 2, size_element, compare, storage);

    /*sorting part*/
    i = index;
    j = m_index;
    k = 0;

    while (i < m_index || j < (index + length))
    {
        if (i < m_index && (compare(array + i * size_element, array + j * size_element) <= 0 || j >= (index + length)))
        {
            memcpy(storage + k * size_element, array + i * size_element, size_element);
            i++;
        }
        else if (j < (index + length) && (compare(array + i * size_element, array + j * size_element)> 0 || i >= m_index))
        {
            memcpy(storage + k * size_element, array + j * size_element, size_element);
            j++;
        }

        k++;
    }

    memcpy(array + index * size_element, storage, length * size_element);
}

Возможно, можно сделать оператор if..else в цикле while функции mergesort_helper более чистым. Если есть 100% уверенность, либо if или же if else правда, можно было бы просто сделать if else заявление else утверждение.

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

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

2. Есть много способов представить срез массива, но в основном вам нужен только указатель на первый элемент и счетчик. Первый элемент базового массива, если вы его знаете, вообще не представляет интереса.

3. Если единственный способ добраться до некоторой памяти — использовать аргумент функции, отметив это restrict позволяет лучше оптимизировать и является хорошей документацией.

4. Вместо остатка в специальном регистре / без остатка при определении половины счетчика просто вычтите обработанный диапазон из целого. Это менее подвержено ошибкам.

5. Ваш код для слияния слишком сложен, потому что вы не обрабатываете все остальное сразу, когда одна из отсортированных последовательностей работает пусто. Это тоже неэффективно.

6. Вам понадобится только половина рабочего пространства, если вы переместите левую последовательность перед слиянием с местом назначения, вместо слияния в рабочем пространстве и копирования результата обратно.

7. В C есть тип, предназначенный для размера объекта и, следовательно, также для индексов массива: size_t.
   Используйте его там, где это необходимо.

8. void*-арифметика (при условии sizeof(void) == 1) является расширением gcc. Нет причин использовать его, так как вы могли бы просто использовать char* вместо этого и строго соответствовать.

9. Функции сравнения в C традиционно возвращают int, значимость меньше, равна или больше нуля. Итак, зачем вам вообще рассматривать что-то еще?

10. Если функция не должна изменять аргументы, передаваемые указателем, пусть тип отражает это. Постоянная корректность позволяет компилятору выявлять ошибки.

11. Рассмотрите возможность добавления typedef, чтобы избежать повторения типа компаратора.

12. Хотя ноль является недопустимым вводом для mergesort_helper(), Я лично считаю, что рассуждать проще, если в защитной оговорке читается < 2 чем == 1.

13. Избегайте слишком длинных очередей. Горизонтальная прокрутка снижает удобочитаемость и, следовательно, ремонтопригодность.

14. Хотя смешивание объявлений и операторов, строго говоря, недопустимо до C99, все уже реализовали это, потому что это очень полезно.

    Отложите объявление переменной до тех пор, пока у вас не будет правильного значения для ее инициализации. Не инициализируйте его произвольным значением и не оставляйте его неинициализированным, если можете. Это позволяет избежать ошибок и упрощает понимание.

typedef int (*comparator)(const void*, const void*);

static void mergesort_helper(
    char* restrict p,
    size_t n,
    size_t s,
    comparator f,
    char* restrict scratch
) {
    if (n < 2) return;
    const size_t mid = n / 2;
    mergesort_helper(p, mid, s, f, scratch);
    mergesort_helper(p + mid * s, n - mid, s, f, scratch);
    memcpy(scratch, p, mid * s);
    char *aa = scratch, *ab = scratch + mid * s, *ba = p + mid * s, *bb = p + n * s;
    while (aa != ab && ba != bb) {
        char** x = f(aa, ba) <= 0 ? &aa : &ba;
        memcpy(p, *x, s);
        p += s;
        *x += s;
    }
    memcpy(p, aa, ab - aa);
}

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

16. Вам действительно следует справиться с нехваткой памяти, хотя бы путем вызова abort().

17. В виде mergesort() это точка входа, я бы установил несколько assert()s для проверки работоспособности во время разработки.

/*
    p   - array to be sorted
    n   - number of elements
    s   - size of each element
    f   - comparator
*/
void mergesort(void * restrict p, size_t n, size_t s, comparator f) {
    assert(s && n <= (size_t)-1 / s && (!n || (f && p)));
    void* scratch = malloc(n / 2 * s);
    if (!scratch && n / 2) {
        fprintf(stderr, "malloc() failed for mergesort().n");
        abort();
    }
    mergesort_helper(p, n, s, f, scratch);
    free(scratch);
}

18. Существует более простой идиоматический способ определить трехстороннее сравнение, даже если простое вычитание не подходит.

19. Не переводите из или в void*. Неявные преобразования работают и менее подвержены ошибкам.

static int compare(const void* pa, const void* pb) {
    const int32_t *a = pa, *b = pb;
    return (*a > *b) - (*a < *b);
}

20. У вас ровно один тестовый пример, и это для типичного случая. Автоматизируйте это (добавив соответствующий is_sorted() tester), и попробуйте с одним и нулевым элементами, по крайней мере, проверить очевидные угловые случаи.

21. Использование неправильного спецификатора формата для printf это ошибка.

22. return 0; неявно для main() с C99.

23. Вернуть ошибку, если ваша программа завершилась с обнаруженной ошибкой.

int is_sorted(const void * restrict p, size_t n, size_t s, comparator f) {
    assert(s && n <= (size_t)-1 / s && (!n || (f && p)));
    if (n--)
        for (const char* q = p; n--; q += s)
            if (f(q, q + s) > 0)
                return 0;
    return 1;
}

static int test(int32_t array[], size_t n) {
    printf("%zu: ", n);
    for (size_t i = 0; i < n; ++i)
        printf("%" PRId32 " ", array[i]);
    printf("n");

    mergesort(array, n, sizeof *array, &compare);

    int res = is_sorted(array, n, sizeof *array, &compare);

    printf(res ? "OK: " : "FAIL: ");
    for (size_t i = 0; i < n; ++i)
        printf("%" PRId32 " ", array[i]);
    printf("n");

    return res;
}

int main() {
    int32_t array[] = {6, 4, 3, 2, 7, -100, 1, 0, 5, 8, -100, 8};

    return !test(array, sizeof array / sizeof *array)
        || !test(array, 1)
        || !test(array, 0)
        || !test(0, 0);
}

Смотрите, как все это собирается вместе жить на колиру.

TL; DR: чтобы повысить производительность при сохранении простоты, переключитесь на сортировку вставкой для небольших массивов.

Поздравляем с выбором слияния! Это отличный выбор. Это очень элегантно, стабильно и может обеспечить отличную производительность без того, чтобы код превращался в ужасный беспорядок, как это обычно бывает с быстрой сортировкой.

Уже есть много ответов, поэтому я выберу другой угол.

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

Один из хороших способов исправить это — проверить размер массива и вместо этого использовать сортировку вставкой, если количество записей ниже предела. Начните с предела 8, а затем попробуйте другие значения позже, если вы хотите настроить производительность.

В качестве альтернативы вы можете написать нерекурсивную версию сортировки слиянием. Все, чего вы добьетесь, — это то, что код станет менее читабельным. Не делай этого! И в любом случае сортировка вставкой выполняет меньше сравнений, чем сортировка слиянием для небольших массивов.

Другой более сложный способ — исследовать тимсорт. Timsort — это современный образец адаптивных алгоритмов слияния. Многие языковые среды выполнения реализуют стандартный алгоритм сортировки как timsort. Однако сложность кода сильно возрастает.

Наконец, если вам нравится экспериментировать, вот последняя идея. Вы могли понять, что внутренние сортировки в настоящее время существуют только в особом случае, когда массив достаточно мал, чтобы поместиться в кеш-память уровня 1 ЦП. Во всех остальных случаях то, что вы делаете, на самом деле является внешней сортировкой. И угадайте, какой алгоритм лучше всего подходит для этой цели? Да, верно, это действительно слияние! Таким образом, вы можете попытаться реализовать k-way mergesort с учетом кеширования или timsort с учетом кеширования. Это привело бы к дополнительным уровням сложности, поскольку вам нужно было бы написать некоторый архитектурно-зависимый код. Но кто знает, к каким результатам приведет такой эксперимент?

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

Во всяком случае, это всего лишь несколько идей, пришедших мне в голову. Делайте то, что вам больше нравится, и получайте удовольствие!