MergeSort, QuickSort or HeapSort?

performance sorting memory-efficient
Manuel picture Manuel · Dec 19, 2013 · Viewed 26.3k times · Source

What are are the relative advantages of the three in terms of the number of comparisons performed and the amount of memory required by the algorithms. Which of them is their running time guaranteed?

Answer

TypeIA picture TypeIA · Dec 19, 2013

I think Wikipedia's coverage of this is pretty thorough and answers all your questions. The comparison table shows the best, average and worst-case performance, the memory usage, and other characteristics like stability.

Related questions

Swift Beta performance: sorting arrays

I was implementing an algorithm in Swift Beta and noticed that the performance was very poor. After digging deeper I realized that one of the bottlenecks was something as simple as sorting arrays. The relevant part is here: let n = 1000000 …

Read More
C# Sort and OrderBy comparison

I can sort a list using Sort or OrderBy. Which one is faster? Are both working on same algorithm? List<Person> persons = new List<Person>(); persons.Add(new Person("P005", "Janson")); persons.Add(new Person("P002", "…

Read More
Performance of qsort vs std::sort?

According Scott Meyers, in his Effective STL book - item 46. He claimed that std::sort is about 670% faster than std::qsort due to the fact of inline. I tested myself, and I saw that qsort is faster :( ! Could anyone help …

Read More