Divide and conquer is an algorithm for solving a problem by the following steps

• Divide recursively the problem into non-overlapping subproblems until these become simple enough to be solved directly

• Conquer the subproblems by solving them recursively. If they are small enough, solve them as base cases

• Combine the solution to the subproblems into the solution for the original problem

## Merge Sort Algorithm

Merge sort is an efficient sorting algorithm using the Divide and conquer algorithm

• It divides the unsorted list into N sublists until each containing one element

• Sort/Conquer the sublists by solving them as base cases, a list of one element is considered sorted

• Repeatedly merge/combine sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list

## Merge Sort implementation example in Java

``````import java.util.Arrays;

public class MergeSortTopDown {
public int[] sort(int[] arr) {
int n = arr.length;
if (n < 2) {
return arr;
}

// divide the array in half
int[] left = Arrays.copyOfRange(arr, 0, n/2);
int[] right = Arrays.copyOfRange(arr, n/2, n);

// sort/conquer each half
int[] sortedLeft = sort(left);
int[] sortedRight = sort(right);

// merge/combine the sorted halves
return merge(sortedLeft, sortedRight, n);
}

private int[] merge(int[] left, int[] right, int n) {
int[] result = new int[n];
int l = 0;
int r = 0;

for (int i = 0; i < n; i++) {
if (l < left.length && (r >= right.length || left[l] < right[r])) {
result[i] = left[l];
l++;
} else {
result[i] = right[r];
r++;
}
}

return result;
}

public static void main(String[] args) {
int[] a = {7, 9, 2, 3, 1};
a = new MergeSortTopDown().sort(a);

Arrays.stream(a).forEach(System.out::println);
}
}
``````