-2

What is the best algorithm to sort a link list [in C/C++]?

poundifdef
  • 18,726
  • 23
  • 95
  • 134
Cory W.
  • 1
  • 1
  • 1
  • 2
    You may have to specify which language you want (C or C++) since the solutions will be quite different. – Greg Hewgill Nov 14 '09 at 06:28
  • 1
    Maybe John can help you out: http://stackoverflow.com/questions/1733420/where-can-i-get-c-c-sample-code-for-merge-sort-a-link-list – Michael Burr Nov 14 '09 at 07:14
  • This is a duplicate of http://stackoverflow.com/questions/1525117/whats-the-fastest-algorithm-for-sorting-a-linked-list – Jørgen Fogh Nov 14 '09 at 10:50
  • There is no "best" algorithm. It depends on your exact circumstances. You might be able to get a working answer if you can describe your environment, your list implementation and the data it will contain. – Holger Just Aug 06 '14 at 17:19

5 Answers5

11

Merge sort is suitable for sorting linked lists. Some details here. Sample C code here.

Why is it suitable? Well, to put it simply, mergesort's main component - the merging of sorted subsequences - can be easily done on two linked lists, because all it ever needs is comparing the head elements, so it doesn't require the random access an array has.

Also, here's an article named A COMPARATIVE STUDY OF LINKED LIST SORTING ALGORITHMS you may find interesting.

Eli Bendersky
  • 263,248
  • 89
  • 350
  • 412
  • I don't know why people keep linking to this site - the implementation sucks as it is overly complicated and needlessly traverses the list; the algorithm in use is equivalent to the iterative array-based version - which is not suited for linked lists as these don't allow random access - and should be replaced with a stack-based implementation; even the vanilla recursive one should perform better – Christoph Nov 14 '09 at 09:45
6

Merge sort.

Better yet, just use std::list and its sort() method.

Pavel Minaev
  • 99,783
  • 25
  • 219
  • 289
  • 1
    Would you like to elaborate the reason for merge sort. Thanks for suggesting STL, but can't use it because it is homework – Cory W. Nov 14 '09 at 06:27
  • 1
    @Cory: of the three common algorithms (heapsort, quicksort, mergesort) it's the only one which performs well without random access – Christoph Nov 14 '09 at 09:57
1

Depends on what you mean by "best". Do you mean quickest to implement, or most efficient runtime? The size and characteristics of what you're sorting also play a role. Sorting 10 items versus sorting 10 million items will likely lead to a different "best" algorithm. For large datasets where "best" means fastest runtime, I like quicksort.

  • I think I remember hearing that quicksort runs slow on sorted (or nearly sorted) data. So, as bpv said, the characteristics of the data would indeed play a large role in your decision. – ialm Nov 14 '09 at 07:26
  • 1
    @veol: A naive quicksort runs slow, most practical implementations use randomized pivoting. – MAK Nov 14 '09 at 07:30
  • @MAK: It seems that I wasn't paying attention in class again :) – ialm Nov 14 '09 at 08:22
1

A stack-based mergesort implementation is the weapon of choice.

Some time ago, I needed to sort a doubly-linked list. Wikipedia told me to use mergesort as it's the only one of the three common general-purpose sorting algorithms (heapsort, mergesort and quicksort) which performs well when random-access is slow and even provided a link to Simon Tatham's implementation.

First, I re-implemented his algorithm, which showed that it was basically the well-known iterative version. It's a bad choice as it relies on random access and therefore performs poorly.

The recursive version is better suited for linked lists as it only needlessly traverses one of the lists when splitting and not both (as does Simon's variant).

What you should use is a stack-based version as this implementation gets entirely rid of unnecessary list traversals.

Christoph
  • 164,997
  • 36
  • 182
  • 240
0

It's worth thinking about how you got to this point. If you're going to need your items sorted in one particular way, consider keeping the list sorted and inserting them directly into the sorted list. That way you don't have to sort it when you need it.

Tim
  • 9,171
  • 33
  • 51