Сортировка слиянием связанный список

Самое простое от Gonnet + Руководство Baeza Yates Алгоритмов . Вы называете его с количеством отсортированных элементов, которые Вы хотите, который рекурсивно разделен пополам, пока это не достигает запроса на размер один список, который Вы тогда просто снимаете с передней стороны исходного списка. Они все объединяются в отсортированный список в натуральную величину.

[Отмечают, что прохладный стековый в первом сообщении называют Сортировкой с объединением Онлайн, и это получает самое крошечное упоминание в упражнении в Knuth Vol 3]

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

В значительной степени основано на ОТЛИЧНОМ коде из: http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html

Слегка обрезано и приведено в порядок:

typedef struct _aList {
    struct _aList* next;
    struct _aList* prev; // Optional.
       // some data
} aList;

aList *merge_sort_list(aList *list,int (*compare)(aList *one,aList *two))
{
    int listSize=1,numMerges,leftSize,rightSize;
    aList *tail,*left,*right,*next;
    if (!list || !list->next) return list;  // Trivial case

    do { // For each power of two<=list length
        numMerges=0,left=list;tail=list=0; // Start at the start

        while (left) { // Do this list_len/listSize times:
            numMerges++,right=left,leftSize=0,rightSize=listSize;
            // Cut list into two halves (but don't overrun)
            while (right && leftSize<listSize) leftSize++,right=right->next;
            // Run through the lists appending onto what we have so far.
            while (leftSize>0 || (rightSize>0 && right)) {
                // Left empty, take right OR Right empty, take left, OR compare.
                if (!leftSize)                  {next=right;right=right->next;rightSize--;}
                else if (!rightSize || !right)  {next=left;left=left->next;leftSize--;}
                else if (compare(left,right)<0) {next=left;left=left->next;leftSize--;}
                else                            {next=right;right=right->next;rightSize--;}
                // Update pointers to keep track of where we are:
                if (tail) tail->next=next;  else list=next;
                // Sort prev pointer
                next->prev=tail; // Optional.
                tail=next;          
            }
            // Right is now AFTER the list we just sorted, so start the next sort there.
            left=right;
        }
        // Terminate the list, double the list-sort size.
        tail->next=0,listSize<<=1;
    } while (numMerges>1); // If we only did one merge, then we just sorted the whole list.
    return list;
}

Примечание: Это гарантировано O (NLog (N)) и использует ресурсы O (1) (без рекурсии, без стека, ничего).

Более простой/чистой реализацией может быть рекурсивная реализация, из которой время выполнения NLog(N) более понятно.

typedef struct _aList {
    struct _aList* next;
    struct _aList* prev; // Optional.
    // some data
} aList;

aList* merge_sort_list_recursive(aList *list,int (*compare)(aList *one,aList *two))
{
    // Trivial case.
    if (!list || !list->next)
        return list;

    aList *right = list,
          *temp  = list,
          *last  = list,
          *result = 0,
          *next   = 0,
          *tail   = 0;

    // Find halfway through the list (by running two pointers, one at twice the speed of the other).
    while (temp && temp->next)
    {
        last = right;
        right = right->next;
        temp = temp->next->next;
    }

    // Break the list in two. (prev pointers are broken here, but we fix later)
    last->next = 0;

    // Recurse on the two smaller lists:
    list = merge_sort_list_recursive(list, compare);
    right = merge_sort_list_recursive(right, compare);

    // Merge:
    while (list || right)
    {
        // Take from empty lists, or compare:
        if (!right) {
            next = list;
            list = list->next;
        } else if (!list) {
            next = right;
            right = right->next;
        } else if (compare(list, right) < 0) {
            next = list;
            list = list->next;
        } else {
            next = right;
            right = right->next;
        }
        if (!result) {
            result=next;
        } else {
            tail->next=next;
        }
        next->prev = tail;  // Optional.
        tail = next;
    }
    return result;
}

NB: Это требует хранения Log(N) для рекурсии. Производительность должна быть примерно сопоставима с другой стратегией, которую я опубликовал. Здесь есть потенциальная оптимизация - запуск цикла слияния while (list && right), и простое добавление оставшегося списка (поскольку нас не особо волнует конец списков; достаточно знать, что они слиты).