11

I have a linked list implementation and I'm experimenting with both Mergesort and QuickSort algorithms.

What I don't understand is why the sort operation in std::list is so fast. Looking at the std::list under linux and it appears to be linked list as well, not an array based list.

The merge sort I tried almost identical to Dave Gamble's version here: Merge Sort a Linked List

Also, I thought I'd try a simple quicksort based on this code: http://www.flipcode.com/archives/Quick_Sort_On_Linked_List.shtml

Suprisingly, to sort 10 million random numbers using std::list and sort was around 10 times quicker than either of those others.

And for those that are asking, yes I need to use my own list class for this project.

Improve this question
8
  • 4
    You could have a look at the code for the std::list implementation ...
    – ChrisWue
    Jul 18, 2011 at 4:21
  • 1
    I have been looking at that code and it's not immediately obvious why it's faster.
    – hookenz
    Jul 18, 2011 at 4:25
  • 1
    One reason i feel std::list is faster than yours because std::list is template based and the code generated will be optimized for the object type you have used.
    – Raghuram
    Jul 18, 2011 at 4:27
  • @Raghuram, The code generated for my list is optimized for my type
    – hookenz
    Jul 18, 2011 at 4:28
  • 1
    Quicksort is going to be slow on lists, it assumes you can very quickly split the list into halves.
    – bdonlan
    Jul 18, 2011 at 4:46

1 Answer 1

Reset to default
15

I've been taking a look at the interesting GLibC implementation for list::sort (source code) and it doesn't seem to implement a traditional merge sort algorithm (at least not one I've ever seen before).

Basically what it does is:

  1. Creates a series of buckets (64 total).
  2. Removes the first element of the list to sort and merges it with the first (i=0th) bucket.
  3. If, before the merge, the ith bucket is not empty, merge the ith bucket with the i+1th bucket.
  4. Repeat step 3 until we merge with an empty bucket.
  5. Repeat step 2 and 3 until the list to sort is empty.
  6. Merge all the remaining non-empty buckets together starting from smallest to largest.

Small note: merging a bucket X with a bucket Y will remove all the elements from bucket X and add them to bucket Y while keeping everything sorted. Also note that the number of elements within a bucket is either 0 or 2^i.

Now why is this faster then a traditionnal merge sort? Well I can't say for sure but here are a few things that comes to mind:

  • It never traverses the list to find a mid-point which also makes the algorithm more cache friendly.
  • Because the earlier buckets are small and used more frequently, the calls to merge trash the cache less frequently.
  • The compiler is able to optimize this implementation better. Would need to compare the generated assembly to be sure about this.

I'm pretty sure the folks who implemented this algorithm tested it thoroughly so if you want a definitive answer you'll probably have to ask on the GCC mailing list.

Improve this answer
5
  • 2
    From your description, here's an alternate conception of what's going on: Visualize a binary counter, representing how many elements have already been merged in. The empty buckets represent zeros, the full buckets ones. This is in fact the same sequence of comparisons as a standard recursive merge sort, but without a ridiculously deep stack or any midpoint scanning. The length of the list currently being worked on is implicit in which buckets they're currently in.
    – Phil Miller
    Jul 18, 2011 at 8:41
  • Is this called a bucket sort?
    – hookenz
    Jul 18, 2011 at 8:46
  • Looks like a modified version of a bucket sort
    – hookenz
    Jul 18, 2011 at 8:47
  • @Matt No, it's not. An item is not assign to a specific bucket to be sorted but will instead progressively move from one bucket to another as the list is being merged. In fact the original code doesn't even mention buckets. I only named the various lists buckets because that's the first intuitive name I came up with (it's also better then the original list __tmp[64]). Like Novelocrat mentioned, it's just a different take on merge sort.
    – Ze Blob
    Jul 18, 2011 at 9:35
  • @Matt I clarified the algorithm a bit. Hopefully it's a bit less confusing now.
    – Ze Blob
    Jul 18, 2011 at 9:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.