Algorithm - Merge Sort

Merge Sort
Merge sort is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output.

Solution
public class MergeSort {

    static int[] tempArr;

    public static void main(String a[]) {

        int[] inputArr = {11, 8, 34, 5, -4, 19, 0, 25, 97, 83, 8};
        sort(inputArr);
        for (int i : inputArr) {
            System.out.print(i);
            System.out.print(" ");
        }
    }

    static void sort(int array[]) {
        tempArr = new int[array.length];
        doMergeSort(array, 0, array.length - 1);
    }

    static void doMergeSort(int[] array, int lowerIndex, int higherIndex) {

        if (lowerIndex < higherIndex) {
            int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
            // Below step sorts the left side of the array
            doMergeSort(array, lowerIndex, middle);
            // Below step sorts the right side of the array
            doMergeSort(array, middle + 1, higherIndex);
            // Now merge both sides
            mergeParts(array, lowerIndex, middle, higherIndex);
        }
    }

    static void mergeParts(int[] array, int lowerIndex, int middle, int higherIndex) {
        for (int i = lowerIndex; i <= higherIndex; i++) {
            tempArr[i] = array[i];
        }
        int i = lowerIndex;
        int j = middle + 1;
        int k = lowerIndex;
        while (i <= middle && j <= higherIndex) {
            if (tempArr[i] <= tempArr[j]) {
                array[k] = tempArr[i];
                i++;
            } else {
                array[k] = tempArr[j];
                j++;
            }
            k++;
        }
        while (i <= middle) {
            array[k] = tempArr[i];
            k++;
            i++;
        }
    }
}

Result
-4 0 5 8 8 11 19 25 34 83 97

Comments

Popular posts from this blog

Clear the app data programmatically in android

convert an integer to a string in java

Print the large string values in android log cat.