Merge Sort Algorithm O n log n Stable Sort is an important DAA topic because it appears in real projects, debugging sessions, and interviews. Learn the meaning first, then connect it to a small working example so the rule does not stay abstract.
For this page, focus on what problem Merge Sort Algorithm O n log n Stable Sort solves, where developers usually make mistakes, and how to verify the result. The audit note for this lesson was: limited checklist/practice/mistake/FAQ notes .
A strong understanding of Merge Sort Algorithm O n log n Stable Sort should include syntax, behavior, one realistic use case, one failure case, and one quick way to check your work with tools or output.
Merge Sort Algorithm O n log n Stable Sort should be studied as a practical algorithm analysis lesson, not as a label. Start by naming the input, the rule that changes the input, and the result a learner should be able to predict after reading the page.
In the daa > merge-sort page, the notes should connect the definition with a working scenario, a mistake that beginners actually make, and the exact check that proves the fix. That makes the topic useful for coding, debugging, and interview revision.
Merge Sort is a classic divide-and-conquer sorting algorithm. It repeatedly divides the array into smaller halves until each part becomes very small, then merges those parts back together in sorted order.
Merge Sort is important because it guarantees O(n log n) time in the best, average, and worst cases. It is also stable, which means equal elements keep their original relative order.
Merge Sort works in two major phases:
The key operation is the merge step, where two already sorted subarrays are combined efficiently.
The array is repeatedly divided in half, so the number of division levels is about log n. At each level, all elements are processed once during merging, which costs O(n).
So the total work is:
O(n) work per level x O(log n) levels = O(n log n)
This is why Merge Sort has the same asymptotic running time in all cases.
| Metric | Best | Average | Worst | Space | Stable? |
|---|---|---|---|---|---|
| Time Complexity | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Recurrence | T(n) = 2T(n/2) + O(n) | - | - | ||
| Recursion depth | O(log n) | - | - |
Consider the array [38, 27, 43, 3, 9, 82, 10].
Final result: [3, 9, 10, 27, 38, 43, 82]
import java.util.Arrays;
public class MergeSort {
static void mergeSort(int[] arr, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
static void merge(int[] arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int[] leftPart = new int[n1];
int[] rightPart = new int[n2];
for (int i = 0; i < n1; i++) leftPart[i] = arr[left + i];
for (int j = 0; j < n2; j++) rightPart[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftPart[i] <= rightPart[j]) {
arr[k++] = leftPart[i++];
} else {
arr[k++] = rightPart[j++];
}
}
while (i < n1) arr[k++] = leftPart[i++];
while (j < n2) arr[k++] = rightPart[j++];
}
public static void main(String[] args) {
int[] arr = {38, 27, 43, 3, 9, 82, 10};
System.out.println("Before: " + Arrays.toString(arr));
mergeSort(arr, 0, arr.length - 1);
System.out.println("After: " + Arrays.toString(arr));
}
}def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
arr = [38, 27, 43, 3, 9, 82, 10]
print("Before:", arr)
print("After:", merge_sort(arr))#include <iostream>
#include <vector>
using namespace std;
void merge(vector<int>& arr, int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
vector<int> leftPart(n1), rightPart(n2);
for (int i = 0; i < n1; i++) leftPart[i] = arr[left + i];
for (int j = 0; j < n2; j++) rightPart[j] = arr[mid + 1 + j];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftPart[i] <= rightPart[j]) arr[k++] = leftPart[i++];
else arr[k++] = rightPart[j++];
}
while (i < n1) arr[k++] = leftPart[i++];
while (j < n2) arr[k++] = rightPart[j++];
}
void mergeSort(vector<int>& arr, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
int main() {
vector<int> arr = {38, 27, 43, 3, 9, 82, 10};
mergeSort(arr, 0, arr.size() - 1);
for (int x : arr) cout << x << " ";
return 0;
}function merge(left, right) {
const result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result.push(left[i++]);
} else {
result.push(right[j++]);
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
let arr = [38, 27, 43, 3, 9, 82, 10];
console.log("Before:", arr);
console.log("After:", mergeSort(arr));Suppose we want to merge [27, 38] and [3, 43].
This merge step is linear in the total size of the two sorted subarrays.
| Step | Compare | Chosen Element | Result So Far |
|---|---|---|---|
| 1 | 27 vs 3 | 3 | [3] |
| 2 | 27 vs 43 | 27 | [3, 27] |
| 3 | 38 vs 43 | 38 | [3, 27, 38] |
| 4 | Left side empty | 43 | [3, 27, 38, 43] |
Merge Sort is stable because when two equal elements are compared during merging, the element from the left subarray is taken first. This preserves the original relative order of equal elements.
Stability matters in applications where records are sorted by multiple keys.
During merging, temporary arrays are usually needed to store the left and right halves. Because of this, standard Merge Sort on arrays requires O(n) extra space.
This is the main tradeoff compared with Quick Sort or Heap Sort.
Merge Sort is especially good for linked lists because:
This is why Merge Sort is often the preferred sorting algorithm for linked-list structures.
Merge Sort does not always need recursion. A bottom-up version starts by merging subarrays of size 1, then size 2, then size 4, and so on. This avoids recursion while keeping the same O(n log n) time complexity.
Merge Sort is a good choice when:
| Feature | Merge Sort | Quick Sort | Heap Sort |
|---|---|---|---|
| Best / Average / Worst | O(n log n) | O(n log n) / O(n log n) / O(n^2) | O(n log n) |
| Extra space | O(n) | O(log n) | O(1) |
| Stable | Yes | No | No |
| Practical strength | Predictable and stable | Usually fastest for arrays | In-place with guaranteed worst case |
1. Define the input for Merge Sort Algorithm O n log n Stable Sort.
2. Apply the rule from the lesson.
3. Compare the actual result with the expected result.
4. Record the fix if the result differs.1. Try empty, missing, duplicate, or invalid data.
2. Identify where Merge Sort Algorithm O n log n Stable Sort changes behavior.
3. Explain the safest correction.
4. Retest the normal path.Memorizing Merge Sort Algorithm O n log n Stable Sort without the situation where it is useful.
Connect Merge Sort Algorithm O n log n Stable Sort to a concrete algorithm analysis task.
Testing Merge Sort Algorithm O n log n Stable Sort only with the perfect input.
Include empty, missing, duplicate, incompatible, or failed cases when relevant.
Changing code before reading the visible symptom or error message.
Inspect the output, state, configuration, or stack trace connected to Merge Sort Algorithm O n log n Stable Sort.
Memorizing Merge Sort Algorithm O n log n Stable Sort without the situation where it is useful.
Connect Merge Sort Algorithm O n log n Stable Sort to a concrete algorithm analysis task.
The common mistake is memorizing syntax without understanding when the behavior changes or fails.
Remember the problem it solves in algorithm analysis, then attach the syntax or steps to that problem.
You can predict the result of a small example, explain a failure case, and choose it over a nearby alternative for a clear reason.
They often copy the syntax but skip the state, input, dependency, selector, route, type, or configuration that controls the behavior.
Explore 500+ free tutorials across 20+ languages and frameworks.