Factors In Deciding A Good Sorting Algorithm
Running Time – How quick is an algorithm? We care about average and worst case scenarios. O(N) is godly, O(NlogN) is the standard, O(N^2) is bad, usually.
Space – How much extra space does a sorting algorithm need? (In-place means no extra space is required, which is good.)
Stable – Will the order of same-data-points be preserved? For example, in [2, 4(a), 1, 5, 4(b), 3] if the first 4 (labeled as 4(a)) ends up before the second 4 (labeled as (4b)) in the sorted array, like [1, 2, 3, 4(a), 4(b), 5], then the sorting algorithm is stable.
Swaps – There’s a cost associated with swapping two elements in an array/list. If swapping is expensive, then we may want to choose an algorithm that does as few swaps as possible.
Is the data already sorted? – Sometimes, the data isn’t randomly organized, which affects how an algorithm performs. For example, maybe we have a sorted list, and add a few numbers at the end of it. Some algorithms do better on mostly-sorted data than others.
Will the data fit in RAM? – Sometimes we have to sort data that’s so huge that it won’t fit into RAM, meaning we need to use a special algorithm that will work on data stored on a hard drive.