0
$\begingroup$

I have an assignment to envision and calculate the possible effects the implementation of a general sorting algorithm that is O(n) time and O(1) space ( assuming general case ) would have on computation and society.

In order to do that, I am trying to estimate how much computation time computers in server farms spend on sorting, and what general orders of magnitude the lengths of lists being sorted fall in. Server farms seem to be the most impactful area to analyze for pertinent effects, but if there are some other areas that people would expect to see an outsize effect, I would appreciate them being called out.

I can then present sets of assumptions with the "new" algorithm being faster at sorting lists at such a length and larger and how much faster than the current state of the art. eg. "If the new algorithm is even with the state of the art for lists of 500 billion items, and increases in time with "n" while the soa increases in time with "log n", and 1/2 trillion item and larger sorts take X% of server-farm computation, you could expect to see computation time for the same tasks reduced by order of magnitude Y%". Once I can get some firm numbers ( not the question here ) on how much electricity server farms use, then I can also electricity usage cost comparisons.

When I researched on the web, I found that an O(n)/O(1) sorting algorithm is considered theoretically possible, but undiscovered to this point. I suspect that there might not be much impact on computation, because there seems to be no incentives put out for someone to come up with such an algorithm ( or a proof that it cannot exist ).

What is a the fastest sorting algorithm for an array of integers? https://en.wikipedia.org/wiki/Sorting_algorithm http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap09.htm#:~:text=We%20have%20now%20introduced%20several,quicksort%20achieves%20it%20on%20average

I have presumed that sorting algorithms in general use, at least for large lists like web search results, are O(n log n) time and O(1) space as a general matter of course. If this is in error, please point it out!

My apologies if this forum is not appropriate for this kind of question. In that case, I would ask for pointers on where I should go with this question.

Thank you.

Improve this question
$\endgroup$
7
  • $\begingroup$ researched on the web, I found that the web knows everything, right and wrong. Please specify or at least quote&attribute your sources. Note that $O(n)$ ordering requires an $O(1)$ operation to establish order between a limited number of items. Think about string comparison. $\endgroup$
    – greybeard
    Commented Jun 27, 2020 at 3:58
  • $\begingroup$ 1) cs.stackexchange.com/questions/18536/… 2) en.wikipedia.org/wiki/Sorting_algorithm 3) staff.ustc.edu.cn/~csli/graduate/algorithms/book6/…. Citing sources is something I should have done in the original post; my apologies. $\endgroup$
    – Kyle
    Commented Jun 29, 2020 at 21:29
  • $\begingroup$ Thank you for supplying the references - improving what begs improvement is the way to go. Note that you can(should!) edit your post(s). $\endgroup$
    – greybeard
    Commented Jun 30, 2020 at 3:02
  • $\begingroup$ (Actual time of sorting used to be an issue when CPU was rented by the minute and tape drives needed operators requiring wages…) $\endgroup$
    – greybeard
    Commented Jun 30, 2020 at 3:04
  • $\begingroup$ You should specify the sorting model you are using. It is NOT possible to have a comparison-based sorting algorithm with a running time smaller than $\Omega(n \log n)$ (i.e., any algorithm that requires $o(n \log n)$ time cannot be correct for sufficiently large inputs since it cannot possibly output all $n!$ permutations of an input sequence with $n$ elements). Linear-time sorting algorithms for other models/assumptions on the collection of elements to sort are known (see, e.g., counting sort and radix sort in the case of polynomially bounded integers). $\endgroup$
    – Steven
    Commented Jul 24, 2020 at 1:32

1 Answer 1

Reset to default
1
$\begingroup$

There is no comparison based sorting algorithm faster than O(n log n). So this is all theory.

There are plenty of situations where sorting an array takes O(n) time. These are special cases, but happen a lot. For example a sorted array. Or a sorted array with few elements changed. And there are cases where sorting the whole array isn’t needed. Like if I see my address book on the screen, apparently sorted - but only the bits that I’m looking up are sorted.

Log n isn’t very large, so O(n) doesn’t mean it’s faster than say Quicksort for anything that is small enough to sort.

Server farms rarely sort. Databases are indexed, and indexes are updated, no sorting needed.

The effect on society would be zero. Some people would be able to handle their computational needs for slightly less money, that’s all the difference.

Improve this answer
$\endgroup$
1
  • $\begingroup$ On the opposite, one could argue that an $O(n\log n)$ comparison-based sorting algorithm does not exist because when $n$ grows, so must the key length, at least proportionally to $\log n$. So the true complexity must be $O(n\log^2n)$. $\endgroup$
    – user16034
    Commented Apr 11, 2023 at 9:29

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.