Merge Sort:

package sort;

import java.util.Arrays;

public class L01_MergeSort {

    public static void mergeSort(int[] arr) {
        // Base case: if array has 1 element, it’s already sorted
        if (arr.length <= 1) {
            return;
        }
        // Split the array into two halves
        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);

        // Recursively sort each half
        mergeSort(left);
        mergeSort(right);

        // Merge the sorted halves
        merge(arr, left, right);
    }

    // Merge two sorted arrays into original array
    private static void merge(int[] arr, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;

        // Compare elements from left and right arrays
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                arr[k++] = left[i++];
            } else {
                arr[k++] = right[j++];
            }
        }

        // Copy remaining elements from left array
        while (i < left.length) {
            arr[k++] = left[i++];
        }

        // Copy remaining elements from right array
        while (j < right.length) {
            arr[k++] = right[j++];
        }
    }

    // Test the merge sort
    public static void main(String[] args) {
        int[] arr = {8, 4, 2, 7, 1, 3, 6, 5};
        System.out.println("Before sorting: " + Arrays.toString(arr));

        mergeSort(arr);

        System.out.println("After sorting:  " + Arrays.toString(arr));
    }
}

Steps:

arr = [8, 4, 2, 7, 1, 3, 6, 5]

Each time mergeSort is called, a new stack frame is created holding its own local copies of arr, mid, left, right (they're all local to that specific call — this is the part people often get confused about, so I'll show it explicitly).

---

PHASE 1: Diving down (all pushes, no pops yet)

Frame 1 pushed: mergeSort([8,4,2,7,1,3,6,5])

local: arr = [8,4,2,7,1,3,6,5]
mid = 4
left  = [8,4,2,7]
right = [1,3,6,5]
→ about to call mergeSort(left)

Stack: [F1]

Frame 2 pushed: mergeSort([8,4,2,7])

local: arr = [8,4,2,7]
mid = 2
left  = [8,4]
right = [2,7]
→ about to call mergeSort(left)

Stack: [F1, F2]

Frame 3 pushed: mergeSort([8,4])

local: arr = [8,4]
mid = 1
left  = [8]
right = [4]
→ about to call mergeSort(left)

Stack: [F1, F2, F3]

Frame 4 pushed: mergeSort([8])

local: arr = [8]
length <= 1 → BASE CASE → return immediately

Stack: [F1, F2, F3, F4] → F4 pops immediately → Stack: [F1, F2, F3]

---

PHASE 2: F3 continues — calls mergeSort(right) next

Back in F3, the call to mergeSort(left=[8]) has now returned. F3's next line is mergeSort(right):

Frame 5 pushed: mergeSort([4])

local: arr = [4]
length <= 1 → BASE CASE → return immediately

Stack: [F1, F2, F3, F5] → F5 pops immediately → Stack: [F1, F2, F3]

Now F3 has both halves sorted ([8] and [4], trivially). F3 executes its final line:

merge(arr=[8,4], left=[8], right=[4])
→ compares 8 vs 4 → writes 4, then 8
→ arr is now mutated in place to [4, 8]

F3 returns (its job is done) → Stack: [F1, F2]

---

PHASE 3: Back in F2 — now calls mergeSort(right)

F2's left array ([8,4]) is now sorted to [4,8] (because left in F2 and arr in F3 point to the same array in memory — F3 sorted it in place). F2 moves to its next line: mergeSort(right).

Frame 6 pushed: mergeSort([2,7])

local: arr = [2,7]
mid = 1
left  = [2]
right = [7]

Stack: [F1, F2, F6]

Frame 7 pushed: mergeSort([2]) → base case → returns immediately
Frame 8 pushed: mergeSort([7]) → base case → returns immediately

Back in F6:

merge(arr=[2,7], left=[2], right=[7])
→ 2 < 7, already in order → arr stays [2,7]

F6 returns → Stack: [F1, F2]

Now F2 has both halves sorted: left = [4,8], right = [2,7]. F2 executes its final line:

merge(arr=[8,4,2,7], left=[4,8], right=[2,7])
→ compare 4 vs 2 → write 2
→ compare 4 vs 7 → write 4
→ compare 8 vs 7 → write 7
→ only 8 left → write 8
→ arr mutated in place to [2, 4, 7, 8]

F2 returns → Stack: [F1]

---

PHASE 4: Back in F1 — the entire left half is done, now do the right half

F1's left (originally [8,4,2,7]) is now sorted to [2,4,7,8]. F1 moves to mergeSort(right) where right = [1,3,6,5].

This repeats the exact same pattern as Phase 1–3, just on [1,3,6,5]:

mergeSort([1,3,6,5])
├── mergeSort([1,3])
│   ├── mergeSort([1]) → base case
│   ├── mergeSort([3]) → base case
│   └── merge([1],[3]) → [1,3] stays as-is
├── mergeSort([6,5])
│   ├── mergeSort([6]) → base case
│   ├── mergeSort([5]) → base case
│   └── merge([6],[5]) → compares 6 vs 5 → becomes [5,6]
└── merge([1,3],[5,6])
    → compare 1 vs 5 → write 1
    → compare 3 vs 5 → write 3
    → compare 5... wait, left exhausted → write remaining right: 5, 6
    → result: [1,3,5,6]

F1's right is now sorted to [1,3,5,6]. Stack back to: [F1]

---

PHASE 5: F1 finishes — the final merge

F1 now has both halves fully sorted:

left  = [2,4,7,8]
right = [1,3,5,6]

F1 executes its last line:

merge(arr, left=[2,4,7,8], right=[1,3,5,6])
compare 2 vs 1 → write 1
compare 2 vs 3 → write 2
compare 4 vs 3 → write 3
compare 4 vs 5 → write 4
compare 7 vs 5 → write 5
compare 7 vs 6 → write 6
compare 7 vs (right exhausted) → write remaining left: 7, 8

result: arr = [1,2,3,4,5,6,7,8]

F1 returns. Stack: [] — empty. Program continues after the original

mergeSort(arr) call.

TC using master formula and recurrence relatioon:

Recurrence relation: cn(constant) + T(n/2) + T(n/2) => 2T(n/2) + cn

So, TC = nlogn

TC Using Normal method:

TC = Total number of recursive calls + work done in each step

Level 0: 1 call, each doing merge() work of size n.

Total work = 1 * n = n

Level 1: 2 calls, each doing merge() work of size n/2.

Total work = 2 * n/2 = n

Level 2: 4 calls, each doing merge() work of size n/4.

Total work = 4 × (n/4) = n

Level k (general): 2^k calls, each doing merge() work of size n/2^k.

Total work = 2^k × (n / 2^k) = n

Number of total recursive calls: Every level, the current size gets divided by b (for merge sort, b = 2, since each call splits the array in half)

Level 0: n

Level 1: n / b

Level 2: n / b²

Level 3: n / b³

.......

Level k: n / b^k

Step 2: Set up the equation

We want to find the level k at which the size finally bottoms out at 1 (can't be divided further into a smaller meaningful piece)

n / b^k = 1

logb(n) = k (taking log base b of both sides)

at what level k does the size shrink down to the smallest possible unit (1)?

So, TC = workdone per level(n) * (total recursive calls) logb(n)