Divide and Conquer

import java.util.Arrays;

public class MergeSort {

    // DIVIDE: split array into two halves
    // CONQUER: recursively sort each half
    // COMBINE: merge the two sorted halves
    static void mergeSort(int[] arr, int left, int right) {
        if (left >= right) return;  // base case: 1 element

        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);       // sort left half
        mergeSort(arr, mid + 1, right);  // sort right half
        merge(arr, left, mid, right);    // combine
    }

    static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] L = Arrays.copyOfRange(arr, left, mid + 1);
        int[] R = Arrays.copyOfRange(arr, mid + 1, right + 1);

        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++];
    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("Before: " + Arrays.toString(arr));
        mergeSort(arr, 0, arr.length - 1);
        System.out.println("After:  " + Arrays.toString(arr));
        // After: [3, 9, 10, 27, 38, 43, 82]
    }
}

/*
 * Recurrence: T(n) = 2T(n/2) + O(n)
 * By Master Theorem (Case 2): T(n) = O(n log n)
 *
 * Space: O(n) auxiliary for temporary arrays
 */

public class MaxSubarray {

    // Divide and Conquer approach — O(n log n)
    static int maxCrossing(int[] arr, int l, int mid, int r) {
        int leftSum = Integer.MIN_VALUE, sum = 0;
        for (int i = mid; i >= l; i--) {
            sum += arr[i];
            if (sum > leftSum) leftSum = sum;
        }
        int rightSum = Integer.MIN_VALUE;
        sum = 0;
        for (int i = mid + 1; i <= r; i++) {
            sum += arr[i];
            if (sum > rightSum) rightSum = sum;
        }
        return leftSum + rightSum;
    }

    static int maxSubarrayDC(int[] arr, int l, int r) {
        if (l == r) return arr[l];
        int mid = (l + r) / 2;
        return Math.max(
            Math.max(maxSubarrayDC(arr, l, mid),
                     maxSubarrayDC(arr, mid + 1, r)),
            maxCrossing(arr, l, mid, r)
        );
    }

    // Kadane's Algorithm — O(n) — simpler and faster
    static int kadane(int[] arr) {
        int maxSoFar = arr[0], maxEndingHere = arr[0];
        for (int i = 1; i < arr.length; i++) {
            maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]);
            maxSoFar = Math.max(maxSoFar, maxEndingHere);
        }
        return maxSoFar;
    }

    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("D&C:    " + maxSubarrayDC(arr, 0, arr.length - 1)); // 6
        System.out.println("Kadane: " + kadane(arr));  // 6
    }
}