4.3.5 Sorting algorithms

Question 1

What is the time complexity of:
Bubble sort
Merge sort

Answer 1

O(n^2)

O(nlog n)

Question 2

What is a merge sort?

Answer 2

It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. The array is recursively divided in two halves till the size becomes 1. Once the size becomes 1, the merge processes comes into action and starts merging arrays back till the complete array is merged.

Question 3

Why is bubble sort n^2?

Answer 3

In each pass through the list n items will be examined;

There will be (at most) n passes through the list;