Salem makes a good point. If you don't need to use a linked list, use an array and sort that (with qsort ... not selection sort!).
I whipped up an imp of a merge sort on a linked list.
Unfortunately it has a bug that, on my machine at least, causes it to segfault if you ask for a list of about 270000 or more.
Haven't been able to ferret it out.
Anyone?
Code:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct Node {
int n;
struct Node *next;
} Node;
Node *merge(Node *a, Node *b) {
Node *result = NULL;
if (!a) return b;
if (!b) return a;
if (a->n <= b->n) {
result = a;
result->next = merge(a->next, b);
}
else {
result = b;
result->next = merge(a, b->next);
}
return result;
}
void split(Node *head, Node **front, Node **back) {
Node *slow = head; // head is never NULL
Node *fast = head->next; // fast moves twice as fast as slow
while (fast) {
fast = fast->next;
if (fast) {
slow = slow->next;
fast = fast->next;
}
}
*front = head;
*back = slow->next;
slow->next = NULL;
}
void merge_sort(Node **head) {
Node *nd = *head, *a, *b;
if (!nd || !nd->next)
return;
split(nd, &a, &b);
merge_sort(&a);
merge_sort(&b);
*head = merge(a, b);
}
void print(Node *nd) {
for ( ; nd; nd = nd->next)
printf("%d ", nd->n);
printf("\n\n");
}
void add(Node **nd, int n) {
Node *newnd = malloc(sizeof *newnd);
if (!newnd) {
perror("add:malloc");
exit(EXIT_FAILURE);
}
newnd->n = n;
newnd->next = *nd;
*nd = newnd;
}
int main(int argc, char **argv) {
int n = 100;
if (argc == 2) n = atoi(argv[1]);
srand(time(NULL));
Node *head = NULL;
for (int i = 0; i < n; i++)
add(&head, rand() % (n * 10));
if (n <= 100) print(head);
merge_sort(&head);
if (n <= 100) print(head);
// allowing OS to free memory...
}