Merge Sort Implementation:

public static void mergeSort(int[] arr, int left, int right) {
    if (left >= right) {
        return;  // Base case: single element
    }
    
    // Divide
    int mid = (left + right) / 2;
    mergeSort(arr, left, mid);        // Sort left half
    mergeSort(arr, mid + 1, right);   // Sort right half
    
    // Conquer (Merge)
    merge(arr, left, mid, right);
}

private static void merge(int[] arr, int left, int mid, int right) {
    // Create temp arrays
    int[] leftArr = Arrays.copyOfRange(arr, left, mid + 1);
    int[] rightArr = Arrays.copyOfRange(arr, mid + 1, right + 1);
    
    int i = 0, j = 0, k = left;
    
    // Merge back into original array
    while (i < leftArr.length && j < rightArr.length) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k++] = leftArr[i++];
        } else {
            arr[k++] = rightArr[j++];
        }
    }
    
    // Copy remaining elements
    while (i < leftArr.length) arr[k++] = leftArr[i++];
    while (j < rightArr.length) arr[k++] = rightArr[j++];
}

// Time Complexity: O(n log n) - Always!
// Space Complexity: O(n) - For temporary arrays
// Stability: Stable sort (maintains relative order)