- Quicksort depends on being able to index (or random access) into an array or similar structure. When that’s possible, it’s hard to beat Quicksort.
- You can’t index directly into a linked list very quickly. That is, if
myList is a linked list, then myList[x], were it possible to write such syntax, would involve starting at the head of the list and following the first x links. That would have to be done twice for every comparison that Quicksort makes, and that would get expensive real quick.
- Same thing on disk – Quicksort would have to seek and read every item it wants to compare.
- Merge sort is faster in these situations because it reads the items sequentially, typically making
log(n) passes over the data. There is much less I/O involved, and much less time spent following links in a linked list.
- Quicksort is fast when the data fits into memory and can be addressed directly. Mergesort is faster when data won’t fit into memory or when it’s expensive to get to an item.
VietMX Staff asked 3 years ago
