Task 1: figuring out the complexity
-----------------------------------

Insertion.java on:
  random inputs: n²
  reversed inputs: n²
  95% sorted inputs: n²
  sorted inputs: n

Quick.java on:
  random inputs: n log n
  reversed inputs: n²
  95% sorted inputs: n log n
  sorted inputs: n²

Merge.java on:
  random inputs: n log n
  reversed inputs: n log n
  95% sorted inputs: n log n
  sorted inputs: n

Arrays.sort on:
  random inputs: n log n
  reversed inputs: n
  95% sorted inputs: n log n
  sorted inputs: n

Task 2: improving quicksort
---------------------------

Do the following changes affect the complexity of quicksort on any kind of
input data? If so, what is it that changes?

  Shuffling the array first: [no] [yes+reason]

 Yes, Reversed and Sorted performance is greatly improved. When pivot-element is the 	first or last element (as it is for Sorted and reversed) the operation of quick sorting in regards to pivot element is increased. LOOK IT UP. Change time complexity to n log n on reversed and sorted arrays. Otherwise n² on sorted or reversed (double check)

  Median-of-three pivot selection: [no] [yes+reason]

Median performs very well on sorted arrays, pivot element is middle value of array and avoids worst case scenario where pivot element is smallest or largest. With median as pivot -> Complexity n lg n, if not worst case n² (n² / 2 ?)

  Insertion sort for small arrays: [no] [yes+reason]

No. Insertion made no significant difference in the tests. I tried insertion at n < 100. It does not change time complexity



Which combination of improvements gives the best result?
If you use insertion sort for small arrays, say what cutoff you used.

[...answer here...]

Insertion didn't work for us. Median worked well with sorted arrays but when combined with shuffle it was useless. So in the end just the shuffle performed best which gives n log n complexity I think.


-----