# How Divide and Conquer Algorithms Are Implemented in TheAlgorithms/Java: 7 Classic Examples

> Explore how TheAlgorithms/Java implements divide and conquer algorithms with 7 classic examples. Learn about binary exponentiation, Strassen matrix multiplication & more.

- Repository: [The Algorithms/Java](https://github.com/TheAlgorithms/Java)
- Tags: deep-dive
- Published: 2026-03-04

---

**TheAlgorithms/Java implements divide-and-conquer algorithms as stateless utility classes with recursive methods that split problems into sub-problems, solve them independently, and merge results, covering everything from binary exponentiation to Strassen matrix multiplication.**

The divide-and-conquer paradigm is a fundamental algorithmic strategy that recursively breaks complex problems into smaller sub-problems until they become trivial to solve. In the TheAlgorithms/Java repository, these algorithms are organized under the `com.thealgorithms.divideandconquer` package, providing clean, textbook implementations that favor readability over micro-optimization. Each class exposes a simple public API—typically a static method—that encapsulates the recursive decomposition and result merging process.

## Median of Two Sorted Arrays

The `MedianOfTwoSortedArrays` class in [`src/main/java/com/thealgorithms/divideandconquer/MedianOfTwoSortedArrays.java`](https://github.com/TheAlgorithms/Java/blob/main/src/main/java/com/thealgorithms/divideandconquer/MedianOfTwoSortedArrays.java) implements an O(log(min(m,n))) algorithm to find the median of two sorted arrays without merging them. The `findMedianSortedArrays` method (lines 17-48) ensures the first array is the smaller one, then uses binary search to partition both arrays until the correct split is found where all left elements are less than all right elements.

```java
int[] a = {1, 3, 8};
int[] b = {7, 9, 10, 11};
double median = MedianOfTwoSortedArrays.findMedianSortedArrays(a, b);
System.out.println("Median = " + median);   // → 8.0

```

## Binary Exponentiation

Located in [`src/main/java/com/thealgorithms/divideandconquer/BinaryExponentiation.java`](https://github.com/TheAlgorithms/Java/blob/main/src/main/java/com/thealgorithms/divideandconquer/BinaryExponentiation.java), this class demonstrates how repeated squaring reduces time complexity from O(n) to O(log n). The `calculatePower` method (lines 18-27) recurses on `y/2` for even exponents, multiplying the base when the exponent is odd. An iterative version `power` (lines 30-40) achieves the same result using bit-shifts for improved performance.

```java
long pow = BinaryExponentiation.calculatePower(5, 6); // 5^6 = 15625
System.out.println(pow);

```

## Counting Inversions via Merge Sort

The `CountingInversions` class in [`src/main/java/com/thealgorithms/divideandconquer/CountingInversions.java`](https://github.com/TheAlgorithms/Java/blob/main/src/main/java/com/thealgorithms/divideandconquer/CountingInversions.java) modifies merge sort to count array inversions in O(n log n) time. The `countInversions` method delegates to `mergeSortAndCount` (lines 33-46), which splits the array recursively. During the merge step in `mergeAndCount` (lines 71-89), each time an element from the right sub-array precedes one from the left, the remaining left elements are added to the inversion count.

```java
int[] arr = {2, 4, 1, 3, 5};
int inv = CountingInversions.countInversions(arr);
System.out.println("Inversions = " + inv);   // → 3

```

## Closest Pair of Points

Implemented in [`src/main/java/com/thealgorithms/divideandconquer/ClosestPair.java`](https://github.com/TheAlgorithms/Java/blob/main/src/main/java/com/thealgorithms/divideandconquer/ClosestPair.java), this algorithm solves the closest pair problem in O(n log n) time. The `closestPair` method (lines 64-84) recursively divides the point set by a vertical line, computes minima for left and right halves, then examines a central "strip" of points. The strip processing (lines 90-139) sorts points by y-coordinate and scans them linearly to find any closer cross-pair.

```java
ClosestPair cp = new ClosestPair(5);
cp.array[0] = cp.buildLocation(2, 3);
cp.array[1] = cp.buildLocation(12, 30);
cp.array[2] = cp.buildLocation(40, 50);
cp.array[3] = cp.buildLocation(5, 1);
cp.array[4] = cp.buildLocation(12, 10);
cp.xQuickSort(cp.array, 0, cp.array.length - 1);
double minDist = cp.closestPair(cp.array, cp.array.length);
System.out.printf("Closest distance = %.3f%n", minDist);

```

## Strassen Matrix Multiplication

The `StrassenMatrixMultiplication` class in [`src/main/java/com/thealgorithms/divideandconquer/StrassenMatrixMultiplication.java`](https://github.com/TheAlgorithms/Java/blob/main/src/main/java/com/thealgorithms/divideandconquer/StrassenMatrixMultiplication.java) implements the famous sub-cubic matrix multiplication algorithm. The `multiply` method handles the base case of 1×1 matrices, then splits inputs via `split`, computes seven products `m1` through `m7` (lines 52-73), and recombines them into quadrants `c11` through `c22` (lines 74-90) before joining them back into the result matrix.

```java
int[][] A = {{1, 2}, {3, 4}};
int[][] B = {{5, 6}, {7, 8}};
StrassenMatrixMultiplication sm = new StrassenMatrixMultiplication();
int[][] C = sm.multiply(A, B);
// C = {{19, 22}, {43, 50}}

```

## Tiling Problem with L-Shaped Tiles

Found in [`src/main/java/com/thealgorithms/divideandconquer/TilingProblem.java`](https://github.com/TheAlgorithms/Java/blob/main/src/main/java/com/thealgorithms/divideandconquer/TilingProblem.java), this algorithm covers a 2^n × 2^n chessboard with one missing square using L-shaped triominoes. The `solveTiling` method initializes the board and invokes `fillBoard`, which handles the base case `size == 1` and otherwise places a central L-tile covering three quadrants, then recurses on all four quadrants (lines 59-97).

```java
int[][] tiled = TilingProblem.solveTiling(8, 2, 3); // 8×8 board, missing at (2,3)
for (int[] row : tiled) {
    System.out.println(java.util.Arrays.toString(row));
}

```

## Skyline Algorithm

The `SkylineAlgorithm` class in [`src/main/java/com/thealgorithms/divideandconquer/SkylineAlgorithm.java`](https://github.com/TheAlgorithms/Java/blob/main/src/main/java/com/thealgorithms/divideandconquer/SkylineAlgorithm.java) computes the contour of overlapping rectangular buildings. The `produceSubSkyLines` method (lines 50-78) recursively splits the point list until size ≤ 2, then merges results using `produceFinalSkyLine` (lines 96-124). The merge discards dominated points—those with the same x but larger y, or right-half points not exceeding the left-half minimum.

```java
SkylineAlgorithm algo = new SkylineAlgorithm();
algo.getPoints().add(new SkylineAlgorithm.Point(1, 5));
algo.getPoints().add(new SkylineAlgorithm.Point(2, 3));
algo.getPoints().add(new SkylineAlgorithm.Point(3, 4));
algo.getPoints().add(new SkylineAlgorithm.Point(4, 2));
java.util.ArrayList<SkylineAlgorithm.Point> skyline = 
        algo.produceSubSkyLines(algo.getPoints());
for (SkylineAlgorithm.Point p : skyline) {
    System.out.println("(" + p.getX() + "," + p.getY() + ")");
}

```

## Summary

- TheAlgorithms/Java organizes divide-and-conquer implementations in the `com.thealgorithms.divideandconquer` package as stateless utility classes with clear recursive structures.
- Each algorithm follows the classic three-step pattern: divide the problem into sub-problems, conquer them recursively, and combine the results.
- Implementations include median finding (O(log n)), binary exponentiation (O(log n)), inversion counting (O(n log n)), closest pair (O(n log n)), Strassen multiplication (O(n^2.81)), tiling problems, and skyline computation.
- All classes expose simple public APIs—typically static methods like `findMedianSortedArrays` or `multiply`—that encapsulate the recursive logic while maintaining readability close to textbook pseudocode.

## Frequently Asked Questions

### What is the time complexity of the closest pair implementation in TheAlgorithms/Java?

The `ClosestPair` implementation achieves O(n log n) time complexity. According to the source code in [`src/main/java/com/thealgorithms/divideandconquer/ClosestPair.java`](https://github.com/TheAlgorithms/Java/blob/main/src/main/java/com/thealgorithms/divideandconquer/ClosestPair.java), the algorithm recursively splits the point array (lines 64-84) and processes a central strip in linear time after sorting by y-coordinate, maintaining the optimal bound for this geometric problem.

### How does the Strassen matrix multiplication differ from standard multiplication in the repository?

Unlike the O(n³) standard matrix multiplication, the `StrassenMatrixMultiplication` class implements the Strassen algorithm which runs in O(n^2.81) time. As implemented in lines 52-90 of [`StrassenMatrixMultiplication.java`](https://github.com/TheAlgorithms/Java/blob/main/StrassenMatrixMultiplication.java), it recursively breaks matrices into quadrants and combines seven specially crafted products (`m1` through `m7`) rather than performing eight multiplications, reducing the asymptotic complexity.

### Can the binary exponentiation implementation handle negative exponents?

The current `BinaryExponentiation` implementation in [`src/main/java/com/thealgorithms/divideandconquer/BinaryExponentiation.java`](https://github.com/TheAlgorithms/Java/blob/main/src/main/java/com/thealgorithms/divideandconquer/BinaryExponentiation.java) handles positive exponents through the `calculatePower` method (lines 18-27) and the iterative `power` method (lines 30-40). For negative exponents, you would need to modify the client code to compute the reciprocal of the positive power result, as the current recursion base case assumes non-negative inputs.

### How does the counting inversions algorithm avoid O(n²) complexity?

The `CountingInversions` class avoids the O(n²) brute-force approach by leveraging a modified merge sort. As shown in lines 71-89 of [`src/main/java/com/thealgorithms/divideandconquer/CountingInversions.java`](https://github.com/TheAlgorithms/Java/blob/main/src/main/java/com/thealgorithms/divideandconquer/CountingInversions.java), the algorithm counts cross-inversions during the merge step in linear time. By counting inversions in the left half, right half, and cross-inversions separately during the O(n log n) merge sort process, the overall complexity remains O(n log n) rather than quadratic.