MergeSort.java

package org.drip.zen.algorithm;

public class MergeSort {

    static void SwapLocations (
        double[] numberArray,
        final int location1,
        final int location2)
    {
        double tempNumber = numberArray[location1];
        numberArray[location1] = numberArray[location2];
        numberArray[location2] = tempNumber;
    }

    static void SplitAndMerge (
        double[] numberArray,
        int startLocation,
        int endLocation)
    {
        if (startLocation == endLocation)
        {
            return;
        }

        if (startLocation == endLocation - 1)
        {
            if (numberArray[startLocation] > numberArray[endLocation])
                SwapLocations (numberArray, startLocation, endLocation);

            return;
        }

        double[] mergedNumberArray = new double[endLocation - startLocation + 1];
        int midLocation = (startLocation + endLocation) / 2;
        int rightStartLocation = midLocation + 1;
        int rightLocation = rightStartLocation;
        int leftStartLocation = startLocation;
        int leftLocation = leftStartLocation;
        int rightEndLocation = endLocation;
        int leftEndLocation = midLocation;
        int mergedArrayLocation = 0;

        SplitAndMerge (numberArray, leftStartLocation, leftEndLocation);

        SplitAndMerge (numberArray, rightStartLocation, rightEndLocation);

        while (leftLocation <= leftEndLocation && rightLocation <= rightEndLocation)
        {
            if (numberArray[leftLocation] < numberArray[rightLocation]) {
                mergedNumberArray[mergedArrayLocation] = numberArray[leftLocation];
                mergedArrayLocation = mergedArrayLocation + 1;
                leftLocation = leftLocation + 1;
            }
            else if (numberArray[leftLocation] > numberArray[rightLocation])
            {
                mergedNumberArray[mergedArrayLocation] = numberArray[rightLocation];
                mergedArrayLocation = mergedArrayLocation + 1;
                rightLocation = rightLocation + 1;
            }
            else
            {
                mergedNumberArray[mergedArrayLocation] = numberArray[leftLocation];
                mergedNumberArray[mergedArrayLocation] = numberArray[rightLocation];
                mergedArrayLocation = mergedArrayLocation + 1;
                leftLocation = leftLocation + 1;
                mergedArrayLocation = mergedArrayLocation + 1;
                rightLocation = rightLocation + 1;
            }
        }

        while (leftLocation <= leftEndLocation)
        {
            mergedNumberArray[mergedArrayLocation] = numberArray[leftLocation];
            mergedArrayLocation = mergedArrayLocation + 1;
            leftLocation = leftLocation + 1;
        }

        while (rightLocation <= rightEndLocation)
        {
            mergedNumberArray[mergedArrayLocation] = numberArray[rightLocation];
            mergedArrayLocation = mergedArrayLocation + 1;
            rightLocation = rightLocation + 1;
        }

        mergedArrayLocation = 0;

        for (int mergedArrayLeftLocation = leftStartLocation; mergedArrayLeftLocation <= leftEndLocation; mergedArrayLeftLocation = mergedArrayLeftLocation + 1)
        {
            numberArray[mergedArrayLeftLocation] = mergedNumberArray[mergedArrayLocation];
            mergedArrayLocation = mergedArrayLocation + 1;
        }

        for (int mergedArrayRightLocation = rightStartLocation; mergedArrayRightLocation <= rightEndLocation; mergedArrayRightLocation = mergedArrayRightLocation + 1)
        {
            numberArray[mergedArrayRightLocation] = mergedNumberArray[mergedArrayLocation];
            mergedArrayLocation = mergedArrayLocation + 1;
        }
    }

    static void SplitAndMerge (
        double[] numberArray)
    {
        SplitAndMerge (numberArray, 0, numberArray.length - 1);
    }

    public static void main (
        String[] input)
    {
        double[] unsortedNumberArray = {6, 1, 5, 7, 9, 2, 8, 4, 3, 12};

        SplitAndMerge (unsortedNumberArray);

        for (int i = 0; i < unsortedNumberArray.length; i = i + 1)
        {
            System.out.println (unsortedNumberArray[i]);
        }
    }
}