Merge sort always performs the same number of operations regardless of whether the input list is already sorted because it does not check for existing order. It follows a strict recursive divide-and-conquer pattern, meaning it divides the list into halves until sublists of one element are reached, and then merges them back together. During merging, it does not assume that any sublist is in order; it compares each element and combines them into a sorted list. This fixed structure means that the number of divisions and the number of comparisons remain consistent for any input. While other algorithms like bubble sort or insertion sort can take advantage of a nearly sorted or already sorted list to exit early, merge sort treats all inputs equally. As a result, it performs log n levels of recursion and n merge operations at each level, giving a total time complexity of O(n log n) no matter the list’s initial state.

Merge sort is a stable sorting algorithm because it preserves the relative order of equal elements during the merge process. When merging two sorted sublists, the algorithm compares the front elements of each list. If the elements are equal, it consistently selects the element from the left (or the first) sublist before the one from the right. This approach ensures that elements that appear earlier in the original list retain their position relative to other equal elements in the final sorted list. This behaviour is especially important when sorting records based on one field but wanting to maintain the order of other fields. For example, when sorting a list of students by age, merge sort will keep students with the same age in the same order they were originally listed. This property of stability makes merge sort particularly useful in multi-level sorting and scenarios where the preservation of original order carries meaning.

Yes, merge sort can be implemented iteratively without using recursion, commonly referred to as bottom-up merge sort. In this version, the algorithm starts by treating each element of the list as a sorted sublist of one item. It then repeatedly merges adjacent pairs of sublists of increasing size—first pairs of 1-element lists, then 2-element lists, then 4-element lists, and so on—until the whole list is merged and sorted. The performance of the iterative approach remains the same as the recursive approach, with a time complexity of O(n log n) and a space complexity of O(n). However, the iterative version avoids the overhead of recursive function calls, which can lead to stack overflow issues with very large datasets. This makes it more memory-efficient in terms of call stack usage, although both versions still require additional memory for merging. In practical terms, iterative merge sort is especially useful in languages or systems with limited stack depth.

Although merge sort consistently has a time complexity of O(n log n), the actual runtime can vary based on several practical factors. One key factor is the overhead of recursive function calls in the traditional implementation. Each recursive call adds to the call stack and incurs a small computational cost. In systems with limited memory or processing power, this can slow down execution. Another factor is the cost of creating and copying temporary arrays during the merge steps. Since merge sort needs to allocate new space each time it merges sublists, frequent memory allocations can impact performance, especially on systems with slow memory management or limited RAM. Additionally, cache usage affects runtime—merge sort may not use the CPU cache as efficiently as in-place algorithms like quick sort or insertion sort. Lastly, programming language and compiler optimisations also influence speed. For example, a well-optimised iterative version in C may run faster than a recursive version in Python despite having the same time complexity.

Merge sort is preferred over quick sort and heap sort in situations where stability, predictability, and external sorting are important. One major advantage of merge sort is its stability, which ensures that elements with equal keys retain their original relative order. This is essential in applications such as multi-level sorting or sorting structured records like databases. Merge sort also guarantees O(n log n) performance in the worst case, while quick sort can degrade to O(n²) if poor pivots are chosen and no optimisations are applied. This makes merge sort more reliable for datasets where worst-case performance must be avoided. Furthermore, merge sort is well-suited for external sorting, where data is stored on disk rather than in memory. Because merge sort accesses data sequentially and processes it in chunks, it minimises disk seeks and is more efficient for sorting large files that cannot fit entirely into RAM. In such scenarios, merge sort’s advantages outweigh its higher space usage.