none
Heap Sort about 15x Faster than QuickSort RRS feed

  • General discussion

  • In todays highly machine instruction-optimised and highly cached Intel & AMD processors, the Heap sort outperforms the QuickSort (by a factor of 15x) - so why does Microsoft claim that they still use the QuickSort for Array.Sort functions etc?.  

    Sunday, November 27, 2011 8:25 PM

All replies

  • The may believe Wikipedia:  "Although somewhat slower in practice on most machines than a well implemented quicksort,"
    Sunday, November 27, 2011 9:21 PM
  • "by a factor of 15x"

    Interesting claim. Can you provide any reference for it?

    Thursday, December 1, 2011 2:36 PM
    Moderator
  • Hi,

    It depends on how much data is needing sorted. QuickSort is fast for smaller data sets; maybe that was their thinking. Who knows. Give both implements a bench test and see what happens at different levels of data.


    "The programmer, like the poet, works only slightly removed from pure thought-stuff. He builds his castles in the air, from air, creating by exertion of the imagination." - Fred Brooks
    Thursday, December 1, 2011 2:47 PM