I wanted to know that if there is a difference between running times and invariants of iterative and recursive merge sort. How to change the Merge sort (iterative or recursive version) in such a way that the best case is the same as in the case of Insertion sort?
If there was Pseudo code it would be much more sense able. However, There is not any difference in running times of iterative or recursive implementation and the only difference is that, the recursive implementation is much more readable and convenient compared to iterative one. both implementations have O(nLogn) running time.
How to change the Merge sort (iterative or recursive version) in such a way that the best case is the same as in the case of Insertion sort
Merge sort is neutral to input that means, either sorted or not sorted input will have O(nLogn) so THERE IS NOT BEST CASE OR WORSE CASE AND ALWAYS O(nLogn).
On the other hand, insertion sort is not neutral to input that means, in best case it has O(n) running time when the input is sorted and in worse case is O(n^2) when input is reverse sorted.
I wanted to know that if there is a difference between running times and invariants of iterative and recursive merge sort.
In computer science, a loop invariant is a property of a program loop that is true before each iteration. link
iterative implementation invariant
curr_size<=n-1
left_start<n-1