Coding Exercise: Merge Sort Using Recursion

Sort array using divide-conquer: split → sort halves → merge.

Example: [64, 34, 25, 12, 22, 11, 90] → [11, 12, 22, 25, 34, 64, 90]

Problem Statement

Input: Unsorted array

Output: Sorted array (ascending)

Stable sort: O(n log n) guaranteed.

Algorithm Steps

1. Divide: split at mid

2. Conquer: recursively sort halves

3. Combine: merge sorted halves

Complete Solution

              
            
C++

          Merge sort implementation
        
#include <iostream>
using namespace std;

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
    
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = 7;
    
    mergeSort(arr, 0, n-1);
    cout << "Sorted: ";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    return 0;
}

Merge Sort Tree: [38, 27, 43, 3]

              
            
TEXT

          Divide-conquer-merge visualization
        
[38,27,43,3]
├── [38,27] ──┬── [38] ── [27] ──→ [27,38]
└── [43,3]  ──└── [43] ── [3]   ──→ [3,43]
                                    ↓
                               [27,38,3,43] → [3,27,38,43]

Test Cases

              
TEXT

          Expected outputs
        
[64,34,25,12,22,11,90] → [11,12,22,25,34,64,90]
[5,2,8,1] → [1,2,5,8]
[1] → [1]

Complexity Analysis

Time: O(n log n) - always

Space: O(n) - temp arrays

Stable: Yes ✓

Practice Variations

1. Bottom-up merge sort (iterative)

2. Merge k sorted arrays

3. Count inversions during merge

Conclusion

Mastered merge sort! Classic divide-conquer algorithm.

Next: Quick sort or tree traversals.