# 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. Jan 22 '16 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. Jan 22 '16 at 17:07
• Use the sorting algorithm that your programming environment provides you. – Yuval Filmus Jan 22 '16 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... – vonbrand Jan 23 '16 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, ... – Maxim Jan 23 '16 at 15:58