When to use merge sort, quick sort, and heap sort effectivly?

[neehakale]

I know that heap sort,quick sort and merg sort are the faster sorting algoritms than the bubble sort,selection sort,shell sort and selection sort.

I got an idea,in which situation we can use bubble sort(use when we have to 100 items: bubble sort is effective),shel l sort is effective when one has to sort near abt 5000 items..selectio n sort is effective for sorting 1000 items...and more than 1000 and less than 5000 items if u have to sort use insertion sorting.

Now my question is heap sort,merg sort and quick sort are used to sort millions of items...hence Can anbody pls tel me....from these 3 sorts which sort to use when?

[weaknessforcats]

Get a copy of Teach Yourself Data Structrures and Algorithms in 24 Hours by Robert LaFore.

I don't wan to rewrite the first 15 chapters here.

[RRick]

A merge sort is used when you don't have enough room in memory to perform the sort. This breaks the file into many smaller files that can be sorted. Once these smaller files are sorted, they are merged back together.

In this age of gigabyte memory, one wonders why anyone would use this technique. But if you're google and need to sort tera-bytes of data, then the merge sort starts to look useful.

Try this link: http://en.wikipedia.or g/wiki/Merge_sort

[Jeckyll]

(sorry for the ghost post- this is more for anyone else who reads this page)

@RRick
Ahhh no way man! Merge sort requires an temporary array the same size of the data being sorted to operate. It is the least memory efficient sort I know of. An in-place merge sort is possible but it pretty much destroys the benefits of merge sort in the first place and is a real bugger to implement.
Also, in this age of 'gigabyte memory' we waste more memory than ever before and attempt to tackle massive mathematical problems. Perhaps your average code monkey may never run out of RAM or storage making java applets but you might find merge sort useful for the following reasons:
> You have a large number of things to sort and enough room to have the auxiliary storage array- and you need a 'stable' sort. It is the ONLY stable O(n*log(n)) sort.
> Merge sort reads sequentially and is unmatched for reading from slow drives, or magnetic tapes.
> Merge sort can be easily threaded due to it's split in half nature, so these days I think it pretty much trumps heap sort (and it's variation smooth sort).

[Jeckyll]

Just an note on quicksort...
A good 3-partition quicksort is the fastest sort- but it not a stable sort. It is brilliant as it's inner loop (repeated many times) can be efficiently implemented on most architectures. It has a worst case scenario of O(n^2) if the array is exactly in reverse order though. A variation of quicksort called intro-sort swaps over to heap sort (pfff) when a bad case is detected but you could also swap over to merge sort... Also, insertion sort is better than quicksort for very small arrays (n<7). On that note, if you're just putting an item into an already sorted array just use insertion sort instead of using the quicksort bazooka to shoot a fish in a barrel!

[Jeckyll]

Oh yeah- bubble sort is crap. Never ever use that awful bloody sort. I really have no idea why it's taught. Rubbish.
If you wanted a very simplified way to choose a sort I would stick with this (which is not infallible) (and I'd welcome criticism and conversation as to why):

> Use Introsort unless...
> n<7, then use Insertion sort...
> you're inserting into an already sorted[],use insertion sort...
> You need a stable sort and can afford the space, use merge sort (and consider threading it :D)
> Swaps are very slow/expensive, use selection sort (don;t look at me like that- it minimises the swaps!)