Sign in to follow this  
Denzin

Sorting linked lists

Recommended Posts

Usually the method provided by the standard library of your language.

In a purely theoretical situation, if the list is almost sorted, insertion sort gets the best complexity. Otherwise, quicksort and merge sort are fairly good choices.

Share this post


Link to post
Share on other sites
I'll second Merge Sort.

Quicksort is slightly easier to implement, but has an awful (n^2) worst-case (which can potentially be abused by hostile users).

However, if you're doing anything other than inserting once in bulk prior to a single sort you'd be much better off with a tree of some form, efficiency (and algorithmic-complexity) wise. Of course, trees are far harder to implement.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this