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.