Sorted array except for first K and last K elements

Question

An array A of size n is known to be sorted except for the first k elements and last k elements where k is a constant. which of the following algorithms is best suited for sorting the array?

 A) Quicksort
 B) Bubble sort
 C) Selection Sort
 D) Insertion Sort

Given answer is D.

unable to understand how this works and also What would have been the answer if Merge sort is also given?

Answer 1

Let's have a look at the complexity of the algorithms:

A) Quicksort: would take worse case O(n²) average O(n log n)
B) Bubble Sort: would take O(n²)
C) Selection Sort: would take O(n²)
D) Insertion Sort: would take O(k* n) if k is constant = O(n)

So D has the best performance. (for each of the k elements: O(log n) to find the position to insert to + O(n) to insert)

But since Quicksort is known to have a small konstant faktor and is in average O(n log n), it is most likely faster for "bigger" k values.

---

Extra:

E) merge sort : would take 2 * O(k log k) + O(n)

• sort the k elements at the front O(k log k)
• sort the k elements at the end O(k log k)
• merge the 3 lists O(n)

Over all that makes for constant k O(n) so based on complexity the same as Insertion Sort.

But if you look at it with k not constant:
merge sort: O(k log k) + O(n)
Insertion Sort: O(k* n)

So insertion sort would be faster.

Arguments against merge sort:
In general merge sort is not inplace (insertion sort is), so you would need extra space or a very clever implemenattion variant that manages to do it inplace without much overhead in complexity.

Answer 2

Since the first K and last K elements are constant in numbers, so it really makes no sense in calculating their complexity as it will be constant.

Comparing all above given algos with their complexity:

A) Quicksort: Worst case O(n²) average O(n log n)

B) Bubble Sort: O(n²)

C) Selection Sort: O(n²)

D) Insertion Sort: O(k* n) if k=constant = O(n)

If the inversion count is O(n), then the time complexity of insertion sort is O(n). In worst case, there can be n(n-1)/2 inversions. The worst case occurs when the array is sorted in reverse order. So the worst case time complexity of insertion sort is O(n2).*

So, Quicksort is best in general but for small List Insertion sort has a Advantage :

Insertion sort is faster for small n because Quick Sort has extra overhead from the recursive function calls. Insertion sort is also more stable than Quick sort and requires less memory.

See Why is Insertion sort better than Quick sort for small list of elements?