Merge Sort is a classic example of the divide and conquer approach. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves.

Diagram:

The array is recursively divided until each sub-array contains a single element. These are then merged in a sorted manner.


public class MergeSort {
    void merge(int arr[], int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;
        int L[] = new int[n1];
        int R[] = new int[n2];
        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];
        int i = 0, j = 0;
        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++;
        }
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }
    void sort(int arr[], int l, int r) {
        if (l < r) {
            int m = (l + r) / 2;
            sort(arr, l, m);
            sort(arr, m + 1, r);
            merge(arr, l, m, r);
        }
    }
}

Explanation:

The function `merge()` is used to merge two halves. The function `sort()` uses recursion to divide the array and call the `merge()` function.

Console Output:

Sorted array: [1, 2, 3, 4, 5, 6]

Quick Sort

Concept:

Quick Sort is another divide and conquer algorithm. It picks an element as a pivot and partitions the given array around the picked pivot.

Diagram:

The array is partitioned into two halves around a pivot element, and the process is repeated for each half.


public class QuickSort {
    int partition(int arr[], int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }
    void sort(int arr[], int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            sort(arr, low, pi - 1);
            sort(arr, pi + 1, high);
        }
    }
}

Explanation:

The `partition()` function places the pivot element at its correct position and places all smaller elements to the left and all greater elements to the right. The `sort()` function recursively sorts the sub-arrays.

Console Output:

Sorted array: [1, 2, 3, 4, 5, 6]

Binary Search

Concept:

Binary Search is a divide and conquer algorithm that finds the position of a target value within a sorted array by repeatedly dividing the search interval in half.

Diagram:

The search space is halved in each step, focusing on the half where the target value is likely to be present.


public class BinarySearch {
    int binarySearch(int arr[], int l, int r, int x) {
        if (r >= l) {
            int mid = l + (r - l) / 2;
            if (arr[mid] == x)
                return mid;
            if (arr[mid] > x)
                return binarySearch(arr, l, mid - 1, x);
            return binarySearch(arr, mid + 1, r, x);
        }
        return -1;
    }
}

Explanation:

The function `binarySearch()` checks the middle element of the array. If it matches the target, it returns the index. Otherwise, it recursively searches the left or right half.

Console Output:

Element found at index: 3

Strassen's Matrix Multiplication

Concept:

Strassen's Algorithm is used for matrix multiplication and reduces the complexity by dividing matrices into sub-matrices and applying the divide and conquer technique.

Diagram:

Matrices are divided into four sub-matrices, and seven multiplications are performed instead of eight.


// Pseudocode representation
void strassenMatrixMultiplication(int A[][], int B[][], int C[][], int size) {
    // Base case when size is 1
    if (size == 1) {
        C[0][0] = A[0][0] * B[0][0];
    } else {
        // Divide matrices into submatrices
        // Compute 7 products using Strassen's formula
        // Combine results into the resultant matrix C
    }
}

Explanation:

Strassen's Algorithm improves the multiplication complexity by reducing the number of recursive multiplications needed, making it faster for large matrices.

Console Output:

Matrix multiplication result: [[...]]

Karatsuba Algorithm

Concept:

Karatsuba Algorithm is a fast multiplication algorithm that uses the divide and conquer technique to multiply two numbers more quickly than the traditional method.

Diagram:

The numbers are split into halves, and three multiplications are performed instead of four.


// Pseudocode representation
long karatsuba(long x, long y) {
    if (x < 10 || y < 10) return x * y;
    int n = Math.max(Long.toString(x).length(), Long.toString(y).length());
    int m = n / 2;
    long a = x / (long) Math.pow(10, m);
    long b = x % (long) Math.pow(10, m);
    long c = y / (long) Math.pow(10, m);
    long d = y % (long) Math.pow(10, m);
    long ac = karatsuba(a, c);
    long bd = karatsuba(b, d);
    long abcd = karatsuba(a + b, c + d);
    return ac * (long) Math.pow(10, 2 * m) + (abcd - ac - bd) * (long) Math.pow(10, m) + bd;
}

Explanation:

The Karatsuba Algorithm reduces the multiplication of two n-digit numbers to at most three multiplications of n/2-digit numbers, significantly increasing efficiency.

Console Output:

Product of numbers: 1234567890