Divide and Conquer in Java

Divide and Conquer is a fundamental algorithm design paradigm in computer science, used to solve various types of problems by dividing them into smaller subproblems, solving the subproblems recursively, and then combining their solutions.

The divide and conquer strategy works by:

1. Dividing the problem into a number of subproblems that are smaller instances of the same problem.
2. Conquering the subproblems by solving them recursively. If the subproblem sizes are small enough, solve them in a straightforward manner.
3. Combining the solutions to the subproblems into the solution for the original problem.

1. Sorting algorithms such as Quick Sort and Merge Sort.
2. Searching algorithms like Binary Search.
3. Complex number multiplication and other number-theoretic problems.
4. Constructing data structures such as Binary Trees and Segment Trees.

Merge Sort is a classic example of divide and conquer.

MergeSort.java

public class MergeSort {
    // Merges two subarrays of arr[]
    void merge(int arr[], int l, int m, int r) {
        // Find sizes of two subarrays to be merged
        int n1 = m - l + 1;
        int n2 = r - m;
 
        /* Create temp arrays */
        int L[] = new int[n1];
        int R[] = new int[n2];
 
        /*Copy data to temp arrays*/
        for (int i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];
 
        /* Merge the temp arrays */
 
        // Initial indexes of first and second subarrays
        int i = 0, j = 0;
 
        // Initial index of merged subarray array
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }
 
        /* Copy remaining elements of L[] if any */
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
 
        /* Copy remaining elements of R[] if any */
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
 
    // Main function that sorts arr[l..r] using merge()
    void sort(int arr[], int l, int r) {
        if (l < r) {
            // Find the middle point
            int m = (l + r) / 2;
 
            // Sort first and second halves
            sort(arr, l, m);
            sort(arr, m + 1, r);
 
            // Merge the sorted halves
            merge(arr, l, m, r);
        }
    }
}