Merge Sort Algorithm in DSA Javascript - Time & Space Complexity

Time Complexity: Merge Sort Algorithm

O(n log n)

Understanding Time Complexity

We want to understand how the time taken by merge sort changes as the list to sort gets bigger.

How does the number of steps grow when the input size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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);
}

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));
}
    

This code splits the array into halves recursively, then merges sorted halves back together.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive splitting and merging of arrays.
• How many times: The array is split about log n times, and merging happens n times at each level.

How Execution Grows With Input

As the input size doubles, the number of splitting levels increases by one, and merging covers all elements each level.

Input Size (n)	Approx. Operations
10	About 10 * 4 = 40 operations
100	About 100 * 7 = 700 operations
1000	About 1000 * 10 = 10,000 operations

Pattern observation: Operations grow roughly as n times log n, which grows faster than linear but slower than quadratic.

Final Time Complexity

Time Complexity: O(n log n)

This means the time grows a bit faster than the size of the input but much slower than checking every pair.

Common Mistake

[X] Wrong: "Merge sort is always slower than simple sorting because it uses recursion."

[OK] Correct: Recursion helps break the problem into smaller parts, making the overall process faster than simple methods like bubble sort.

Interview Connect

Understanding merge sort's time complexity shows you can analyze efficient algorithms and explain why they work well for sorting large data.

Self-Check

"What if we changed merge sort to split the array into three parts instead of two? How would the time complexity change?"