# Sort complexity in a random array

if I have an unsorted array with the length of $10^6$, which is filled with absolutely different float numbers, which sorting algorithm would be the best to use and why? And which one would be the worst? InsertionSort, QuickSort, MergeSort, HeapSort, BucketSort? And would it be a difference if the float values would be integers and the array would not have the length of $10^6$, but $10^7$ or even $10^9$ or if it's not an array but a linked list?

• 1. What research have you done? There's lots written about this. See, e.g., cs.stackexchange.com/q/18536/755 and sorting. There would be little point in us repeating standard material -- instead, you should do research before asking and use that to ask a more narrowly crafted question. We expect you to do a significant amount of research before asking and to show us in the question what you've done. See cs.stackexchange.com/help/how-to-ask.
– D.W.
Commented Jan 22, 2016 at 17:06
• 2. Please define "best". By what metric? Fastest in practice? Best asymptotic complexity in theory? Smallest amount of extra memory? Works well with arrays that are too large to store in memory?
– D.W.
Commented Jan 22, 2016 at 17:07
• Use the sorting algorithm that your programming environment provides you. Commented Jan 22, 2016 at 19:40
• @YuvalFilmus, unless OP's performance requirements are extreme, in which case you should look at e.g. Knuth's TAoCP, volume 3. Or see if there is something in the data order that could provide help. Or consider Knuth's observation that perhaps much sorting isn't the right solution... Commented Jan 23, 2016 at 0:42
• By best I meant, the fastest one. I've done research, but I only found examples which of them would work faster in generall. But I have haven't found any information in differences between float and integer numbers. And I haven't found any sources that points out which of them works better on arrays of the amount of indexes 10 to the power of 6, 7, 8, ... Commented Jan 23, 2016 at 15:58