HelloKoding

Practical coding guides

Divide and Conquer Algorithm Example in Java with Merge Sort

In this article, you will learn about Divide and Conquer algorithm example in Java with Merge Sort

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

Let’s see a specific example

Merge Sort

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

Implementation example

MergeSortTopDown.java

package com.hellokoding.algorithm;

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);
    }
}
Follow HelloKoding