1

I need to sort a doubly Linked List using anything but insertion sort, that also runs in a better time then O(n^2). I was thinking about using a quicksort, but was having problems with understanding the algorithm. Could you point me towards any easy to understand documentation that could help me get started?

AstroCB
  • 12,337
  • 20
  • 57
  • 73
Andrew Webb
  • 35
  • 3
  • 6
    [Video of Quicksort visualization using Hungerian folk dance](http://www.youtube.com/watch?v=ywWBy6J5gz8). – Niklas B. Mar 26 '12 at 22:24
  • 2
    Are you allowed to extract it into a different data structure to sort it, or are you required to sort it in place? Extracting to an array, performing quick sort, and putting back into linked list should be something like 2n+nlogn, which is still less than n squared. – captncraig Mar 26 '12 at 22:25
  • No, I cannot use any other data structure to store the nodes. – Andrew Webb Mar 26 '12 at 22:29
  • Are you sure you're allowed to use Quicksort? It runs in *average-case* linear time, but worst-case *quadratic* time, so it might not be what your professor had in mind. – ruakh Mar 26 '12 at 23:11

1 Answers1

2

I would actually recommend a merge sort. It feels like it makes more sense with a doubly linked list, and it has a runtime of O(n log n). Basically, you find the middle and split the list in half, sort each half by itself, and then combine the two in linear time.

There is a thread here that has a pretty good working implementation in c++, that may not be the easiest for you to read if you are learning java, but may be a good starting point.

There is also an excellent high level description of the algorithm at this site.

Community
  • 1
  • 1
captncraig
  • 22,118
  • 17
  • 108
  • 151
  • The important point is that the *worst case* runtime is also `O(n*log n)`, in contrast to quicksort. Also, it's easy to implement :) – Niklas B. Mar 27 '12 at 16:11