
public class MergeSort {
  public static void mergeSort(int[] array, int left, int right) {
    if (left < right) {
      int mid = (left + right) / 2;
      mergeSort(array, left, mid);
      mergeSort(array, mid + 1, right);
      merge(array, left, mid, right);
    }
  }

  private static void merge(int[] array, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int[] leftArray = new int[n1];
    int[] rightArray = new int[n2];
    for (int i = 0; i < n1; ++i)
      leftArray[i] = array[left + i];
    for (int j = 0; j < n2; ++j)
      rightArray[j] = array[mid + 1 + j];
    int i = 0, j = 0;
    int k = left;
    while (i < n1 && j < n2) {
      if (leftArray[i] <= rightArray[j]) {
        array[k] = leftArray[i];
        i++;
      } else {
        array[k] = rightArray[j];
        j++;
      }
      k++;
    }
    while (i < n1) {
      array[k] = leftArray[i];
      i++;
      k++;
    }
    while (j < n2) {
      array[k] = rightArray[j];
      j++;
      k++;
    }
  }
}

Time Complexity

Merge Sort has a time complexity of O(n log n), making it efficient for large datasets.

Space Complexity

The space complexity is O(n) due to the temporary arrays used in merging.

Quick Sort

Overview

Quick Sort is a highly efficient sorting algorithm that uses a divide and conquer approach to sort elements by partitioning an array into two parts.

Partitioning

The key process in quick sort is partitioning, which ensures that all elements before the pivot are less than the pivot and all elements after the pivot are greater.


public class QuickSort {
  public static void quickSort(int[] array, int low, int high) {
    if (low < high) {
      int pi = partition(array, low, high);
      quickSort(array, low, pi - 1);
      quickSort(array, pi + 1, high);
    }
  }

  private static int partition(int[] array, int low, int high) {
    int pivot = array[high];
    int i = (low - 1);
    for (int j = low; j < high; j++) {
      if (array[j] < pivot) {
        i++;
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
      }
    }
    int temp = array[i + 1];
    array[i + 1] = array[high];
    array[high] = temp;
    return i + 1;
  }
}

Time Complexity

The average time complexity of Quick Sort is O(n log n), but it can degrade to O(n^2) in the worst case.

Space Complexity

The space complexity is O(log n) due to the recursive call stack.

Binary Search

Overview

Binary Search is a divide and conquer algorithm used to find the position of a target value within a sorted array.

Procedure

The algorithm repeatedly divides the search interval in half, comparing the middle element with the target value.


public class BinarySearch {
  public static int binarySearch(int[] array, int target) {
    int left = 0, right = array.length - 1;
    while (left <= right) {
      int mid = left + (right - left) / 2;
      if (array[mid] == target)
        return mid;
      if (array[mid] < target)
        left = mid + 1;
      else
        right = mid - 1;
    }
    return -1;
  }
}

Time Complexity

Binary Search has a time complexity of O(log n), making it very efficient for searching in sorted arrays.

Space Complexity

The space complexity is O(1) since it uses a constant amount of space.

Strassen's Matrix Multiplication

Overview

Strassen's Algorithm is a divide and conquer method for matrix multiplication that is more efficient than the standard algorithm.

Algorithm Steps

1. Divide each matrix into four submatrices.

2. Recursively calculate seven matrix products.

3. Combine these products to get the final matrix.


public class StrassenMatrixMultiplication {
  public static int[][] multiply(int[][] A, int[][] B) {
    int n = A.length;
    int[][] result = new int[n][n];
    if (n == 1) {
      result[0][0] = A[0][0] * B[0][0];
    } else {
      int[][] A11 = new int[n/2][n/2];
      int[][] A12 = new int[n/2][n/2];
      int[][] A21 = new int[n/2][n/2];
      int[][] A22 = new int[n/2][n/2];
      int[][] B11 = new int[n/2][n/2];
      int[][] B12 = new int[n/2][n/2];
      int[][] B21 = new int[n/2][n/2];
      int[][] B22 = new int[n/2][n/2];
      // Divide matrices into submatrices
      // Compute the 7 products using Strassen's formulas
      // Combine the 7 products to get the final result
    }
    return result;
  }
}

Time Complexity

Strassen's algorithm has a time complexity of approximately O(n^2.81), which is faster than the conventional O(n^3) complexity.

Space Complexity

The space complexity is higher due to the additional matrices used in the calculation.

Karatsuba Multiplication

Overview

Karatsuba Multiplication is an efficient algorithm for multiplying large numbers by using a divide and conquer approach.

Algorithm Steps

1. Split the numbers into two halves.

2. Perform three multiplications instead of four.

3. Combine the results to get the final product.


public class KaratsubaMultiplication {
  public static long karatsuba(long x, long y) {
    int num1Length = getLength(x);
    int num2Length = getLength(y);
    int maxNumLength = Math.max(num1Length, num2Length);
    if (maxNumLength < 10)
      return x * y;
    maxNumLength = (maxNumLength / 2) + (maxNumLength % 2);
    long m = (long) Math.pow(10, maxNumLength);
    long b = x / m;
    long a = x - (b * m);
    long d = y / m;
    long c = y - (d * m);
    long z0 = karatsuba(a, c);
    long z1 = karatsuba((a + b), (c + d));
    long z2 = karatsuba(b, d);
    return z0 + ((z1 - z0 - z2) * m) + (z2 * (long)(Math.pow(10, 2 * maxNumLength)));
  }

  private static int getLength(long num) {
    return String.valueOf(num).length();
  }
}

Time Complexity

Karatsuba's algorithm has a time complexity of O(n^log3), which is approximately O(n^1.585), making it more efficient than the traditional O(n^2).

Space Complexity

The space complexity is higher due to recursive calls and splitting of numbers.