New answers tagged

0 votes

Correctness proof of bubble sort(bogus proof)

BubbleSort can be expressed in a few different ways, I'm assuming you're referring to something similar to wikipedias formulation. The mistake in your proof is that you assume that sorting an $n + 1$ ...
Knogger's user avatar
  • 710
2 votes

Is it possible to sort numbers in linear time and constant extra space?

If you require a comparison-based sorting algorithm akin to quicksort and merge sort, the answer is "No." Simply put, it can be proven that sorting an array of $n$ elements using a ...
Ziad Ismaili Alaoui's user avatar
0 votes

Is it possible to sort numbers in linear time and constant extra space?

(Note: This was posted before their edit.) Yes. Move all elements with value $-2^{31}$ to the front, order of the remaining elements doesn't matter. Easy in linear time. Then move all remaining ...
Kelly Bundy's user avatar
0 votes

Isn't counting sort a better sorting algorithm for linked lists rather than merge sort?

A recursive bucket sort can have time complexity O(n*log(k)/log(n)). The space needed is O(n).
Michael Hennebry's user avatar
0 votes

Isn't counting sort a better sorting algorithm for linked lists rather than merge sort?

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 ...
user23013's user avatar
  • 478
13 votes
Accepted

Isn't counting sort a better sorting algorithm for linked lists rather than merge sort?

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 ...
Jörg W Mittag's user avatar
7 votes

Isn't counting sort a better sorting algorithm for linked lists rather than merge sort?

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 ...
Stef's user avatar
  • 495

Top 50 recent answers are included