How can I sort a linked list in C ?

Question

Hi,

Need to be able to either sort or insert entries to a linkedlist in alphabetical order.

Is there a good way to do that?

Answer 1

mergesort is fine for the sorting (the insertion in the already-sorted list is even simpler of course, if that's what you're asking about).

Answer 2

You can use the qsort() function in libc. Essentially, you'll create an array of pointers to your nodes, and write a node comparison function... You'd then call qsort() and finally re-create your list in the new order specified by qsort().

Answer 3

You may want to start with sorting by hand, and get an idea how you would sort, then, see if you can get that written in a psuedo-code. From there it would be easy to convert that to a program.

To get help with homework it helps if you explain how you want to do the sort, show some code that isn't working, and explain what it should do, and what it is doing, and then you may find help more forthcoming.

Since you are using a linked list, if you can do a binary tree then a binary sort, esp if you can sort while inserting, would be your best bet.

Answer 4

One can implement a version of quicksort for a single-linked list, but normally this is only interesting as a puzzle, since mergesort is much easier to implement and works equally well (or better) for sorting linked lists.

Answer 5

Inserting is easy, just step through the list till you find the right place, put your new node there (the previous node now links to the new node, the new node to the node the previous node previously pointed to).

If you already have an unsorted list, there is no efficient way to sort it within the list, which means you have to create a second collection and sort there, e.g. using a binary tree or an array and quicksort.

Answer 6

If you have your list already sorted and want to insert a whole lot of items, it may be better to insert them at the beginning and sort afterwards; if you want to insert only a few items it may be better to keep the list sorted.

My reasoning:

• Insertion at the beginning is O(1);
• Insertion keeping the list sorted is O(N);
• Sorting the list is O(N log N) (at best)

So, the whole lot of items above is, therefore, log N items or more and the only a few items is less than log N items.

Answer 7

Ideally, try to keep the linked list sorted while inserting new items.

However, this question was answered, one way or the other, on the following StackOverflow posts:

Inserting a node into a linked list in constant-time?

How do you insert into a sorted linked list?

Sort a singly Linked list

What’s the fastest algorithm for sorting a linked list?

Sorting a linked list

Answer 8

This is not something you should reimplement yourself (unless this is a homework question...). I use glib, which implements a linked list and sorted insert so you don't have to. Here's the appropriate glib documentation.

Answer 9

If your list is doubly-linked, you can turn it into a binary tree and then back into a linked list again.

This requires no auxilliary storage.

Sorting a linked list by turning it into a binary tree