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);
    }
}
Algorithm