Merge Sort | Algorithm | Pseudocode | Dry Run | Code | Strivers A2Z DSA Course

Main ideas / lessons conveyed

• Merge Sort is a divide-and-conquer sorting algorithm based on two core operations:
  • Divide: split the array into two halves (left and right).
  • Merge: combine the two sorted halves into one sorted array.
• Compared to simpler sorting methods (like bubble, insertion, selection), merge sort is presented as more optimized, with better time complexity.
• Teaching flow in the lecture:
  1. Explain the merge sort algorithm conceptually (with examples).
  2. Provide pseudocode using indexes (low, high) rather than creating new subarrays.
  3. Do a dry run (recursion trace) to clarify the process.
  4. Provide a merge procedure and show how to code it (C++ mentioned; other languages referenced via links).

---

Methodology / algorithm (instruction-style)

A) Merge Sort (high-level process)

• Goal: Sort an array of length n using recursion and merging.
• Use recursion to repeatedly:
  • Divide the array segment into two smaller segments:
    • Left half: from low to mid
    • Right half: from mid + 1 to high
  • Recursively sort each half.
  • Merge the two sorted halves back into the original segment from low to high.

B) Divide step (how indices are chosen)

• Compute the midpoint:
  • mid = (low + high) / 2 (integer division)
• Left segment: [low, mid]
• Right segment: [mid + 1, high]

C) Base case (when recursion stops)

• Stop when the segment contains one element:
  • if low == high, return
• Also mentioned: for safety, stop if low >= high since no further splitting is useful.

D) Merge Sort recursion flow (dry-run concept)

• The recursion goes deep first (keeping the left side split repeatedly).
• Once base cases are reached, it returns upward:
  • when both halves are sorted, merge them
• Each merge produces a sorted segment that participates in the larger merges higher in the recursion stack.

---

Merge procedure (detailed instructions)

Inputs

• arr (the main array)
• low, mid, high define:
  • Left sorted subarray: arr[low..mid]
  • Right sorted subarray: arr[mid+1..high]

Merge steps

• Create a temporary array (or list) temp.
• Initialize pointers:
  • left = low
  • right = mid + 1
• While both pointers are within bounds:
  • Condition: while left <= mid and right <= high
  • Compare:
    • If arr[left] <= arr[right]:
      • append arr[left] to temp
      • increment left
    • Else:
      • append arr[right] to temp
      • increment right
• After the loop, copy remaining elements:
  • append the rest of the left half (if anything remains)
  • append the rest of the right half (if anything remains)
• Copy temp back into arr[low..high]:
  • for i from low to high:
    • arr[i] = temp[i - low]

---

Pseudocode / coding structure (as described)

mergeSort(arr, low, high)
  if low >= high: return
  compute mid
  mergeSort(arr, low, mid)
  mergeSort(arr, mid+1, high)
  merge(arr, low, mid, high)

merge(arr, low, mid, high)
  create temp
  merge using two pointers as detailed above
  write back to arr

---

Time complexity and space complexity (as stated)

• Time complexity:
  • Splits happen across about log2(n) levels.
  • Each level does merging work proportional to O(n).
  • Overall: O(n log n) (best/average/worst claimed).
• Space complexity:
  • Uses an auxiliary temporary array during merging.
  • Worst-case auxiliary space: O(n).

---

Speakers / sources featured

• Speaker/Presenter: An instructor from “Strivers A2Z DSA Course” (lecture-style tutorial presented by the Striver channel/instructor).