Sorted array except for first K and last K elements

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.