Sorting linked lists in C [closed]

Question

I was asked to write a function that takes 3 unsorted linked lists and returns one single sorted linked list that combines all three lists. What is the best way you can think of?

I don't really have restrictions of memory, but what would you do with/without memory restrictions?

Answer 1

One option would be to use merge sort on all three of the linked lists, then use one final merge step to merge them together into an overall sorted list.

Unlike most O(n log n) sorting algorithms, merge sort can run efficiently on linked lists. At a high-level, the intuition behind merge sort on a linked list is as follows:

1. As a base case, if the list has zero or one elements, it's already sorted.
2. Otherwise:
   1. Split the list into two lists of roughly equal size, perhaps by moving odd elements into one list and even elements into the other.
   2. Recursively use merge sort to sort those lists.
   3. Apply a merge step to combine those lists into one sorted list.

The merge algorithm on linked lists is really beautiful. The pseudocode works roughly like this:

1. Initialize an empty linked list holding the result.
2. As long as both lists aren't empty:
   1. If the first element of the first list is less than the first element of the second list, move it to the back of the result list.
   2. Otherwise, move the first element of the second list to the back of the result list.
3. Now that exactly one list is empty, move all the elements from the second list to the back of the result list.

This can be made to run in O(n) time, so the overall complexity of the merge sort is O(n log n).

Once you've sorted all three lists independently, you can apply the merge algorithm to combine the three lists into one final sorted list. Alternatively, you could consider concatenating together all three linked lists, then using a giant merge sort pass to sort all of the lists at the same time. There's no clear "right way" to do this; it's really up to you.

The above algorithm runs in Θ(n log n) time. It also uses only Θ(log n) memory, since it allocates no new linked list cells and just needs space in each stack frame to store pointers to the various lists. Since the recursion depth is Θ(log n), the memory usage is Θ(log n) as well.

---

Another O(n log n) sort that you can implement on linked lists is a modification of quicksort. Although the linked list version of quicksort is fast (still O(n log n) expected), it isn't nearly as fast as the in-place version that works on arrays due to the lack of locality effects from array elements being stored contiguously. However, it's a very beautiful algorithm as applied to lists.

The intuition behind quicksort is as follows:

1. If you have a zero- or one-element list, the list is sorted.
2. Otherwise:
   1. Choose some element of the list to use as a pivot.
   2. Split the list into three groups - elements less than the pivot, elements equal to the pivot, and elements greater than the pivot.
   3. Recursively sort the smaller and greater elements.
   4. Concatenate the three lists as smaller, then equal, then greater to get back the overall sorted list.

One of the nice aspects of the linked-list version of quicksort is that the partitioning step is substantially easier than in the array case. After you've chosen a pivot (details a bit later), you can do the partitioning step by creating three empty lists for the less-than, equal-to, and greater-than lists, then doing a linear scan over the original linked list. You can then append/prepend each linked list node to the linked list corresponding to the original bucket.

The one challenge in getting this working is picking a good pivot element. It's well known that quicksort can degenerate to O(n²) time if the choice of pivot is bad, but it is also known that if you pick a pivot element at random the runtime is O(n log n) with high probability. In an array this is easy (just pick a random array index), but in the linked list case is trickier. The easiest way to do this is to pick a random number between 0 and the length of the list, then choose that element of the list in O(n) time. Alternatively, there are some pretty cool methods for picking an element at random out of a linked list; one such algorithm is described here.

---

If you want a simpler algorithm that needs only O(1) space, you can also consider using insertion sort to sort the linked lists. While insertion sort is easier to implement, it runs in O(n²) time in the worst case (though it also has O(n) best-case behavior), so it's probably not a good choice unless you specifically want to avoid merge sort.

The idea behind the insertion sort algorithm is as follows:

1. Initialize an empty linked list holding the result.
2. For each of the three linked lists:
   1. While that linked list isn't empty:
      1. Scan across the result list to find the location where the first element of this linked list belongs.
      2. Insert the element at that location.

---

Another O(n²) sorting algorithm that can be adapted for linked lists is selection sort. This can be implemented very easily (assuming you have a doubly-linked list) by using this algorithm:

1. Initialize an empty list holding the result.
2. While the input list is not empty:
   1. Scan across the linked list looking for the smallest remaining element.
   2. Remove that element from the linked list.
   3. Append that element to the result list.

This also runs in O(n²) time and uses only O(1) space, but in practice it's slower than insertion sort; in particular, it always runs in Θ(n²) time.

---

Depending on how the linked lists are structured, you might be able to get away with some extremely awesome hacks. In particular, if you are given doubly-linked lists, then you have space for two pointers in each of your linked list cells. Given that, you can reinterpret the meaning of those pointers to do some pretty ridiculous sorting tricks.

As a simple example, let's see how we could implement tree sort using the linked list cells. The idea is as follows. When the linked list cells are stored in a linked list, the next and previous pointers have their original meaning. However, our goal will be to iteratively pull the linked list cells out of the linked list, then reinterpret them as nodes a in binary search tree, where the next pointer means "right subtree" and the previous pointer means "left subtree." If you're allowed to do this, here's a really cool way to implement tree sort:

1. Create a new pointer to a linked list cell that will serve as the pointer to the root of the tree.
2. For each element of the doubly-linked list:
   1. Remove that cell from the linked list.
   2. Treating that cell as a BST node, insert the node into the binary search tree.
3. Do an in-order walk of the BST. Whenever you visit a node, remove it from the BST and insert it back into the doubly-linked list.

This runs in best-case O(n log n) time and worst-case O(n²). In terms of memory usage, the first two steps require only O(1) memory, since we're recycling space from the older pointers. The last step can be done in O(1) space as well using some particularly clever algorithms.

You could also consider implementing heap sort this way as well, though it's a bit tricky.

---

Hope this helps!