The worst case running times of Insertion sort, Merge sort and Quick sort,…

Answer: Θ(n^2) for insertion sort, Θ(n log n) for merge sort, and Θ(n^2) for quick sort.

• Insertion sort — worst case Θ(n^2): when the input is in reverse order each insertion may need to shift many elements, producing on the order of n^2 comparisons/movements.

• Merge sort — worst case Θ(n log n): the algorithm always splits the array and merges; there are about log n levels of recursion and each level merges Θ(n) work, giving Θ(n log n) overall.

• Quick sort — worst case Θ(n^2): if pivot choices lead to extremely unbalanced partitions (for example always picking the smallest or largest element on already sorted input), recursion depth becomes linear and total work grows to Θ(n^2). Note that quick sort's average case is Θ(n log n), but the question asks for worst-case.