fastest algorithm for sorting numbers

You are given: A collection of numbers stored in memory.

You should: Return that same collection, but every element is sorted into an order.

Question: What is the fastest way of doing it?

Time cost of operations: Reading memory, writing into memory, Arithmetics (+-×÷) , comparing values (which, on hardware level, is just a minus)

Definitions:

1. fast can mean: least time on average, least time in best case (rarely useful), least time in worst case

2. We care about how much 'extra' time you need, if the amount of numbers inside a collection increases. (for example, if the algorithm needs to do x more 'steps' for 1 more element inside the collection, then the time is equal to x*steps.

Example for an algorithm: comparing every element with every other. Then write values into memory -> Cost?
If collection grows from n elements to m elements, then new time is (m! + m) because (m comparisons * m-1 comparisons * m-2...), then writing into memory.

Go ahead with suggestions. Does not need to be fast, just ideas for ways to sort numbers

Well the fastest is merge sort, which goes something like this:
Split all values into arrays, with one value in each array. Than merge each array with the next one. To merge two arrays, compare the first values, than put the winner in the front of the new array and compare the loser to the next element in the winner's array, then do the same with that winner and that loser. Continue merging the arrays like this until you are left with a single sorted array.

the average time for this is proportional to n*log(n)

One way to do it might be to find a good partner, get married, and then have many children; and then assign them the task of sorting the numbers, once they have all reached sixth grade.

It's a slow method but perhaps more fun than most!

However, come to think of it, it would be pretty expensive.

But you know what they say: we get what we pay for!

.sort() function
Uses the same sorting system as quick sort lol

The fastest actually depends
If there is a very very long list of numbers, of course the fastest is the racing test or something where it checks each value starting from 1, and whichever is the “first” aka the number is lesser would be placed in the first

Natural Mergesort sounds like a strong contender. According to Wikipedia it's stable, worst-case O(n log(n)), and has no extra demand of storage space. There are linear-time algorithms but they typically require extra space.

There is AI ??......
Use it.......
Why do you need to sort numbers ?.........

@Cedur216 said ^

Natural Mergesort sounds like a strong contender. According to Wikipedia it's stable, worst-case O(n log(n)), and has no extra demand of storage space. There are linear-time algorithms but they typically require extra space.

Linear time functions exist? I didn't know that. Could you give an example?

@TheCaptain7777 said ^

Natural Mergesort sounds like a strong contender. According to Wikipedia it's stable, worst-case O(n log(n)), and has no extra demand of storage space. There are linear-time algorithms but they typically require extra space.

Linear time functions exist? I didn't know that. Could you give an example?

Bucket sort(桶排序) is quasi-linear , it is O(a*(n+b) ) with a=longest length of numbers and b=amount of different buckets

Merge sort feels kindof counterintuitive to me, because I still keep comparing stuff. For example, why not compare 3 at a time, or 5 at a time? Or the entire set at a time...

This is what I mean: to find largest element out of 2, I need 1 comparison. To find element out of 3, I need at most 2 comparisons and so forth. So I do not actually increase any speed, right?

2nd ly, that is not how humans sort (cards, for example), we always take one card and place it inside another pile comparing from beginning.

Worst case Time to find correct position for an element in an ordered array is O( log(n) ) -> basically search in the middle, then their middle, etc.

So time for finding all positions should be log(1) + log(2)...+log(n) ?

slee.py

from threading import Thread
from time import sleep

nums = [2,5,3,1,4]
threads = [Thread(target=lambda n:(sleep(n), print(n)),args=(n,)) for n in nums]
[thread.start() for thread in threads]
[thread.join() for thread in threads]

$ python slee.py
1
2
3
4
5

@tors42 said ^

If ykyk, this is epic xD