Which sorting method has best perfomance in terms of storage and time complexity?

Answer 1

Quicksort will usually be the best performing sort. However, quicksort has a worst-case time complexity of O(n2), which may not be reasonable in a real world application. Heapsort is often used in place of quicksort in these cases, as it has a worst-case of O(n log n).

The last of the "big three" sorts is mergesort, which excels in a few areas. Mergesort is trivially easy to parallelize, which is increasingly useful as multi-CPU machines become more and more common. Mergesort is also a stable sort, which may or may not be useful for a given application.

Answer 2

Introspective sort (introsort) is the algorithm of choice, with a worst-case time-complexity of O(n log n) and space complexity of O(log n). Introsort is an adaptive (hybrid) algorithm that starts with a quicksort then degrades to heapsort. Pivot selection during quicksort is critical to best performance, however both quicksort and heapsort are unstable algorithms.

If stability is required, timsort is a better option, with a time-complexity of O(n log n) and a space complexity of O(n). Timsort is derived from merge sort and insertion sort, both of which are stable sorts.

Stability is important when equal objects must remain in the same order they were input. Although this seems immaterial, equality typically applies to the primary sort key only. If an object has more than one sort key then we can we can sort a set of objects in a variety of ways depending on which key we choose to be the primary key. Having sorted by one key and then choosing another, we would (rightly) expect the previous primary key to become the secondary key of the next sort (the previous secondary key should then become the tertiary key, and so on). With a stable sort we don't need to consider secondary sort keys because the secondary sort order is implied from the input order.

For example, when sorting files we have a choice of keys to sort by, such as file name, type, size, date and so on. If we sort the files by name, then we'd expect the files to be in alphanumeric order. However, if we then sort by file extension we'd expect all files with the same extension to remain in alphanumeric order.

A stable sort guarantees this because the secondary key (the file name) is implied from the input order (the output from the previous sort becomes the input for the next sort).

An unstable sort cannot guarantee this unless we keep track of the input order and then use that order as an explicit secondary key. To achieve this, our objects would require a mutable index field so that we could index objects according to their current order. Aside from the time required to set the object indices before we begin sorting, it over-complicates the comparison operations because we now have to take the secondary key into account when comparing two objects with the same primary key. With a stable sort we don't care if primary keys are equal because the two objects must already be in the correct order, it's only the ones that are not equal we have to worry about.