Question

out of the following four:

1.Bubble sort
2. Insertion sort
3. Quicksort
4. Mergesort

a. Which sorting methods perform best and worst for data sizes ≥ 25,000 when
the input data is random?
b. Which sorting methods perform best and worst for data sizes ≥ 25,000 when
the input data is 90% sorted?
c. Which sorting methods perform best and worst for data sizes ≥ 25,000 when
the input data is reverse sorted?
d. Which sorting methods perform best and worst for data sizes < 25,000 when
the input data is random?
e. Which sorting methods perform best and worst for data sizes < 25,000 when
the input data is 90% sorted?
f. Which sorting methods perform best and worst for data sizes <25,000 when the
input data is reverse-sorted?
g. What is the relationship between the running time and the data size for each
of the sorting methods when the input data is random? (Try to come up with a function –
need not be ‘exact’, but close)
 Bubble sort
 Insertion sort
 Mergesort
 Quicksort
h. Conclude which sorting method is better suited for data size >25,000 and under
what input data pattern (random, almost sorted and reversely sorted)

Answer 1

The time complexity of the sorting algorithm listed in different scenario are:

Algorithm	Random	Sorted	ReverseSorted
Bubble	n2	n2	n2
Insertion	n2	n	n2
Quick	n logn	n2	n2
Merge	n logn	n logn	n logn

The graph for n, n², n logn are give below:

It is clear from graph that there is no significant changes in nature of graph at n = 25000 and so, the nature of algorithm would be same.

It is noted that  

Now, Answering the question based on above results and table.

a) and d) For random input data,

Best: QuickSort, MergeSort
Worst: InsertionSort, BubbleSort.

b) and e) For Sorted (90% sorted is approx same as completely sorted)

Best: InsertionSort,
Worst: QuickSort, BubbleSort.

c) and f) For Reverse Sorted

Best: MergeSort
Worst: InsertionSort, BubbleSort, QuickSort.

The answer to question g) is already given in table.

h) Insertion Sort have time complexity O(n) for almost sorted (or sorted) data set. Hence it is most suited.

Hope it helps.