OSDev.org

By George, I think he's got it! Lol! Yes, I did, thank God! If anyone ever has trouble with this and needs help, feel free to pm me. That was a real to hell and back ASM crash course. Onward to the kernel, Wentworth, march! lol... *Gets black stripe on his n00b not-quite-a-ninja white belt*

DavidBG wrote:

Combuster wrote:Seriously, if you are expert enough

This is a little off-topic, but why does your quiz there say a heapsort is the best suited sorting algorithm for embedded realtime devices over a quicksort?

I always used quicksort, should I change to heapsort?

David

Quicksort's worst case conditions are pathological. Heapsort is always O(n log n), but in general runs slower. The best solution is something like STL does: if it determines it's going to run in horrid time, it switches from quicksort to heapsort.

Merge sort is typically considered to be faster than heapsort without sharing quicksort's worst case condition problem. The problem with merge sort is that it wastes a lot of memory unless you start consdering in-place merging - but that's when you start running into other problems. Introsort is a compromise between quicksort and heapsort where the algorithm will automatically switch to heapsort once the recursion depth is too big. Although quicksort is a stable sort, heapsort is not so you cannot guarantee that your sorting will be stable or not in advance. You can easily modify the algorithm so it will tell you. You can find more about introsort here.

EDIT: I usually use a modification of the introsort algorithm I've come up with where I use the smoothsort variation of heapsort. Since quicksort does part of the job and smoothsort comes closer to O(n) when the input is partially sorted, the results are considerably better.

Thanks for the added information.

Combuster clarified this for me via PM, so as not to change the topic too much.

David