2
$\begingroup$

I have to analyze how every sorting algorithm's complexity would change if it had to sort a linked list and which of all of them is the most efficient. I find everywhere that merge sort is the most efficient one for linked lists, but I don't understand why counting sort isn't better. I think it would still be O(n). Am I missing something? Same with bucket sort and radix sort, would the complexity change with a linked list?

$\endgroup$
6
  • $\begingroup$ The complexity of counting sort depends on the range of the integers to sort. Furthermore, what do you mean by sorting a linked list? We can copy a linked list of length $n$ into an array in $O(n)$ time, sort the array and then built back the sorted list in $O(n)$, so each algorithm can sort in the same complexity of standard arrays because linked lists are less powerful than arrays so we can't do better for sure. $\endgroup$
    – SilvioM
    Feb 7 at 15:07
  • 1
    $\begingroup$ it was a question that appeared in a past final exam so I don't think they expect something so trivial like copy the linked list to an array. $\endgroup$
    – Zumikya
    Feb 7 at 15:09
  • $\begingroup$ @Zumikya Did the exam question give any indication of what measure of performance you were to consider? In terms of big oh complexity no comparison-based sort can do better than $\mathcal{O}(n \log n)$, and as Silvio pointed out you can usually convert between container representations within $\mathcal{O}(n)$; converting before and after is always going to be subsumed in the complexity of any algorithm that isn't sub-linear. So the the optimal big-oh complexity is always going to be the same on arrays or linked lists, which suggests they want a different measure than big-oh complexity. $\endgroup$
    – Ben
    Feb 8 at 1:53
  • $\begingroup$ @Zumikya Or do they want you to consider non-optimal implementations? $\endgroup$
    – Ben
    Feb 8 at 1:57
  • 1
    $\begingroup$ If the sort is to be accomplished by rearranging the existing nodes -- neither changing their assigned values nor creating or destroying any -- then Counting Sort is not even an option. It cannot do such a rearrangement. $\endgroup$ Feb 8 at 22:27

5 Answers 5

14
$\begingroup$

You are comparing apples and orange-colored bicycles here.

Merge Sort is a stable Comparison Sort. As such, it only requires that there must be a Total Preorder over the elements.

Comparison Sorts have a lower bound asymptotic worst-case step complexity of $\mathcal{O}(n\log{}n)$. Therefore, Merge Sort's asymptotic worst-case step complexity is as good as it gets for Comparison Sorts. There cannot be a Comparison Sort with a better asymptotic worst-case step complexity.

Counting Sort is a Non-Comparison Sort. Non-Comparison Sorts can be faster than Comparison Sorts, but they can only do this by exploiting some additional information or structure about the inputs that makes them less general than Comparison Sorts.

For example, Counting Sort can only sort small non-negative integers, but has an asymptotic worst-case step complexity of $\mathcal{O}(n + |r|)$, where $|r|$ is the size of the range of possible inputs. Merge Sort can sort elements drawn from an arbitrarily large range, such as integers, which is something Counting Sort cannot do.

Radix Sort can sort anything that can be ordered lexicographically. Its asymptotic worst-case step complexity is $\mathcal{O}(wn)$, where $w$ is the length of the sort key. Merge Sort can sort elements based on an arbitrarily large sort key, which is something Radix Sort cannot do.

Bucket Sort works by distributing the elements into buckets, then sorting those buckets using a Comparison Sort. The worst-case is when all elements end up in the same bucket, in which case Bucket Sort simply degrades to whatever sorting algorithm is used to sort the buckets. Since the sorting algorithm for the buckets is a Comparison Sort, its asymptotic worst-case step complexity cannot be better than $\mathcal{O}(n\log{}n)$, and thus neither can Bucket Sort's.

Typically, Bucket Sort is used with an Insertion Sort for sorting the buckets, which has an asymptotic worst-case step complexity of $\mathcal{O}(n^2)$.

In order to actually reap the benefits of Bucket Sort, a priori knowledge about the distribution of inputs is required.

In other words, unless you have some additional a priori knowledge about the elements of the linked list, you can only use Comparison Sorts, and Counting Sort, Radix Sort, Bucket Sort, and friends are not even an option.

$\endgroup$
6
  • $\begingroup$ I wouldn't say that radix sort can't sort arbitrarily large keys, it's rather that it requires some ability to split keys up into parts or "digits" (which must have the property that the order of keys with non-equal leading digits can be computed solely from the leading digits). Just about anything can be split up that way, but it's a different (and more complicated) requirement from just having an ordering function. $\endgroup$
    – Ben
    Feb 8 at 1:33
  • 5
    $\begingroup$ Also note for readers: the famous $\mathcal{O}(n \log n)$ lower bound on comparison sorts is a bound on the number of comparisons. If you're sorting small things like machine-level integers, doubles, etc, then one comparison is a cheap constant step. But if you're sorting large variable-size things like strings or complex data structures, then one comparison is itself often involves a (variable) number of steps. When comparing comparison to non-comparison sorts; be careful that complexity bounds you're comparing are actually bounds on the same measure of "steps". $\endgroup$
    – Ben
    Feb 8 at 1:45
  • 2
    $\begingroup$ @Ben: If comparison is $\mathcal{O}(k)$ for some key size k, then the bound is $\mathcal{O}(kn \log n) < \mathcal{O}(kn \log kn)$, so it still works as a loose bound if you reinterpret $n$ as $kn$ (i.e. interpret $n$ as the total size of all keys, instead of the number of keys). This is not the conventional interpretation, but quantifying in terms of the total volume of data (ignoring the shape of that data) is not wholly unreasonable. Alas this does not work if your keys are nonlinear to compare, but I've never heard of such a comparison function. $\endgroup$
    – Kevin
    Feb 9 at 2:30
  • $\begingroup$ @Kevin: String compares hopefully have an early-out if they differ (although most sorts compare strings that are lexicographically close so the early-out might only be after the first word of a few bytes). Anyway, worst-case for a given k is long identical prefixes, best case is uniform random distribution at each character position. For many use-cases, I'd guess there are enough different prefixes to at least make the early passes do a lot of early outs. So typical average case might be closer to O(n log n) than to O( kn log kn) (or to O(kn log n)?) $\endgroup$ Feb 9 at 5:07
  • $\begingroup$ @JörgWMittag - The other thing Counting Sort can't do is sort structs that have data other than the sort key. Such as linked-list nodes, as John Bollinger commented under the question. Radix Sort could, perhaps even sorting pointers to list nodes and then rewriting their links later so they don't have to be destroyed and recreated. $\endgroup$ Feb 9 at 5:18
7
$\begingroup$

Counting sort is a very particular kind of sort which you can only apply in particular circumstances.

  • If the elements you're sorting are floating-point numbers instead of integers, counting sort doesn't work.
  • If the elements you're sorting take their values in a huge range with more possible elements than actual elements in the list, then counting sort is probably not worth it (and would have a high space complexity in addition to time complexity).
  • If the elements you're sorting are not numbers, but complex objects with one number field that you're sorting on, then counting sort doesn't make any sense (although bucket sort would be a possible generalisation for that case).

If you find yourself in a particular situation where counting sort can apply, sorting n integers taking value in range [1, k], then:

  • Merge sort has time complexity O(n log(n)) and space complexity O(n);
  • Counting sort has time complexity O(n + k) and space complexity O(n + k).

If you find yourself in this particular situation and if k and n are such that k ∈ O(n), then counting sort is more efficient than merge sort.

$\endgroup$
0
$\begingroup$

There is nothing wrong. Counting sort is definitely better in the sense of having a lower time complexity if the integers have a fixed range. And they very likely had a fixed range when you generated the data, even if you didn't realize it.

But remember what a lower time complexity means: It will eventually be faster than the algorithm with higher time complexity with a large enough n. Your n is just not large enough. It might be discouraging if you pick an n much smaller than the range, as counting sort may appear significantly worse. But just try again using an n so that you will wait for minutes for it to finish. There isn't anything that deep here.

$\endgroup$
0
$\begingroup$

A recursive bucket sort can have time complexity O(n*log(k)/log(n)). The space needed is O(n).

$\endgroup$
0
$\begingroup$

I've found that counting sort is usually faster than mergesort or quicksort as long as k (the absolute difference between the largest and smallest element) is within an order of magnitude of n (the length of the list). Personally I would only use counting sort if k was within 2*n, and only if I really needed the boost in runtime performance. I've never been in a situation where I needed this.

Keep in mind that this would still take up quite a bit of extra space.

It is possible (though not advisable) to make counting sort work with non-integer types such as floating-point numbers, or even strings - but only if you're willing to write your own custom logic to map integers to non-integer values (ordinary hashing wouldn't work because it's not reversible). Again, I can't see this as being useful in most real-world situations, and the space complexity would probably be horrible.

However, there are some hypothetical situations where counting sort/pigeonhole sort would be a no-brainer. The most obvious would be if you knew ahead of time that the integers to be sorted were distinct and that, when sorted, they would compose a sequence of the form min, min+1, min+2...max. In such a case, you would only need to compute the min and max and generate a list of integers within that range in a loop.

In fact, if you knew that min was 0 in this case, you wouldn't even need to compute max, or even look at the source list's elements at all; you could just output all integers from 0 to n-1 with a simple loop.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.