A bottom up NATURAL mergesort for linked lists.

bottomup-natural-queuesort.c

/* 
     
    a very fast bottom up natural mergesort 
    A full description of the algorithm can be found on
    http://www.maxgcoding.com/queue-mergesort-a-comparison-optimal-bottom-up-sort-for-linked-lists/
    
    (C) 2023 Max Goren
    
    Permission is hereby granted, free of charge, to any person obtaining a copy of this 
    software and associated documentation files (the “Software”), to deal in the Software 
    without restriction, including without limitation the rights to use, copy, modify, merge, 
    publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons 
    to whom the Software is furnished to do so, subject to the following conditions:

    The above copyright notice and this permission notice shall be included in all copies or 
    substantial portions of the Software.

    THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING 
    BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 
    NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, 
    DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 
    OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/

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

struct node {
    int info;
    struct node* next;
};

typedef struct node* link;

link newnode(int info, link next) {
    link q = malloc(sizeof *q);
    q->info = info;
    q->next = next;
    return q;
}

void print(link head) {
    for (link it = head; it != 0; it = it->next) {
        printf("%d ", it->info);
    }
    printf("\n");
}

//merge two sorted lists
link merge(link a, link b) {
    struct node dummy; link c = &dummy;
    while (a != 0 && b != 0) {
        if (a->info < b->info) {
            c->next = a; a = a->next; c = c->next;
        } else {
            c->next = b; b = b->next; c = c->next;
        }
    }
    c->next = (a == 0) ? b:a;
    return dummy.next;
}

link sort(link head) {
    int qsize = 255; //should be modified based on list size, if there are no sorted runs > length 1, the queue will need O(n) space.
    int front = 0;
    int back = 0;
    link queue[qsize];
    //decompose list into a queue of sorted runs.
    while (head != 0) {
        link t = head;
        while (head != 0 && head->next != 0)
            if (head->info < head->next->info) head = head->next;
            else break;
        if (head->next != 0) {
            link q = head->next; head->next = 0; head = q;
        } else head = head->next;
        queue[back] = t; back = (back+1) % qsize;
    }
    //merge lists from queue, placing result back on queue until there is only 1 item on queue
    while (abs(front - back) != 1) {
        link a = queue[front]; front = (front+1)%qsize;
        link b = queue[front]; front = (front+1)%qsize;
        head = merge(a, b);
        queue[back] = head; back = (back+1)%qsize;
    }
    //last item left on the queue is the sorted list.
    return queue[front];
}

int main() {
    link head = 0;
    for (int i = 0; i < 9; i++)
        head = newnode(rand() % 100, head);
    print(head);
    head = sort(head);
    print(head);
}