Help verifying Big O

Hey so I am trying to verify some of the sorting algorithms.

• Insertion Sort

• Mergesort

• Quicksort using “median of three” partitioning and cutoff of 10 (using Insertion Sort for the small array portions)

Analysis:

The worst case running time for Insertion Sort was discussed to be O(n²), with actual running time O(n) for sorted input (as long as the inside loop is properly coded). Mergesort was discussed to be O(n log n) for all input. Quicksort using the “median of three” partitioning and a reasonable cutoff was discussed to be O(n Log(n)) for all input, but faster in practice than Mergesort. Do your timings validate these computations?

note that N = Max/2 , and 2N = MAX

After running the programs, i found that

The开发者_Python百科 diff for insertion sorted with sorted max/2 is 0.000307083129882812
The diff for insertion sorted with sorted max is 0.000623941421508789
The diff for insertion reverse with sorted max/2 is 0.000306129455566406
The diff for insertion reverse with sorted max is 0.000745058059692383
The diff for insertion random with sorted max/2 is 2.39158606529236
The diff for insertion random with sorted max is 9.72073698043823
The diff for merge sort with sorted max/2 is 0.00736188888549805
The diff for merge sort with sorted max is 0.0154471397399902
The diff for merge reverse with sorted max/2 is 0.00730609893798828
The diff for merge reverse with sorted max is 0.0154309272766113
The diff for merge random with sorted max/2 is 0.0109999179840088
The diff for merge random with sorted max is 0.0232758522033691
The diff for quick sorted with sorted max/2 is 3.10367894172668
The diff for quick sorted with sorted max is 12.5512340068817
The diff for quick reverse with sorted max/2 is 3.09689497947693
The diff for quick reverse with sorted max is 12.5547797679901
The diff for quick random with sorted max/2 is 0.0112619400024414
The diff for quick random with sorted max is 0.0221798419952393

I know that the insertion sort is working correctly since for the random, i did 9.72073698043823/ 2.39158606529236 ~= 4 = 2² = O(n²)

but I don't know how to verify if the others ones are O(n Log(n)) or not. Please help

---

Let me remind you that f(n)=O(n) means limit when n grows very big that f(n)/n => constant

What is not said :

• that constant can be very big
• that for small values, it means something : e.g. 10^9/n+n is O(n) but for n=1, it0s 10^9+1 ;-)
• O(something) is not the argument killer, topology of your data may sometime affect the algorithm (e.g: on "almost" sorted data, bubble sort performs well)

If you want to draw conclusions, run test with big samples relevant for your application, don't draw conclusion too early (note that modern CPU might fool you with cache, pipelining and multicore if you use it (what you can for sorting)