-1

For large arrays the answer is usually quicksort if we want in place sort, or merge sort if we want guaranteed O(nlogn)

However for small arrays insertion sort is faster than the above.

Is there a different absolute shortest way to sort exactly 8 elements?

Or is insertion sort the way to go?

Makogan
  • 8,208
  • 7
  • 44
  • 112
  • If you want guaranteed O(n log n) without using O(n) extra space, look to heapsort. – Jim Mischel Jun 08 '18 at 04:29
  • 1
    There are optimal [sorting networks](https://en.wikipedia.org/wiki/Sorting_network) for small values of n. You write a series of `if ... else` statements. A little searching should get you to an optimum 8-item sort. – Jim Mischel Jun 08 '18 at 04:32

1 Answers1

1

Asymptotic analysis does not apply for any fixed number. You will need to choose a cost model and analyze it. For example, for a small number like 8 elements, there is very likely a sorting network that's fully optimized for a given cost: perhaps comparisons, or max parallelism.

It's like asking how long a piece of string is: you haven't fixed enough assumptions.

In the real world, for these kinds of sizes, all kinds of effects show up: for example, cache behavior.

nimish
  • 4,755
  • 3
  • 24
  • 34
  • I am asking algorithmically, what is the fastest algorithm that sorts exactly 8 elements – Makogan Jun 08 '18 at 03:37
  • 1
    That question makes no sense. If you fix 'N' then every finite algorithm will run in constant time for some constant, which depends on the algorithm chosen. You need to chose something to minimize (comparisons, element swaps, etc); then you can optimize (i.e., what's your cost model?) – nimish Jun 08 '18 at 03:46
  • The number of steps it takes to execute an algorithm determines its theoretical runtime, Which is what is used to determine the asymptotic complexity of the algorithm, it very much makes sense. – Makogan Jun 08 '18 at 04:20
  • 1
    @Makogan Actually, he's right: if N is fixed, then asymptotic analysis is irrelevant because running time is constant. If you say that the algorithm is O(N^2), and N is fixed at 8, then the running time is O(64), which is a constant. And since in asymptotic analysis we ignore constants, the answer to "What is the algorithmic complexity of sorting 8 items with bubble sort" is "O(1)." – Jim Mischel Jun 08 '18 at 04:36
  • @JimMischel The asymptotic analysis is irrelevant but not the complexity analysis, the number of instructions executed can still be analyzed – Makogan Jun 08 '18 at 05:35
  • 1
    @Makogan Number of instructions is heavily dependent on the implementation. But in any case, if you want to know *the best* way for *your* use-case is to code it up and measure! We could argue all day about what method *could* be fastest. – kmdreko Jun 08 '18 at 10:42