Labels

algorithms (22) Design Patterns (20) java (19) linux (14) Snippet (13) service mix (6) soa (4)

Merge Sort in Java

  private static void sortList(Integer[] toSortArray) {
        Integer[] sortedArray = new Integer[toSortArray.length];
        mergeSortList(toSortArray, sortedArray, 0, toSortArray.length - 1);
    }
    private static void mergeSortList(Integer[] toSortArray, Integer[] sortedArray, int low, int high) {
        if (low >= high)
            return;
        int mid = (high + low) / 2;
        mergeSortList(toSortArray, sortedArray, low, mid);
        mergeSortList(toSortArray, sortedArray, mid + 1, high);
        mergeResults(toSortArray, sortedArray, low, mid, high);
        printArray(toSortArray);
    }
    private static void mergeResults(Integer[] toSortArray, Integer[] sortedArray, int low, int mid, int high) {
        for (int index = low; index <= high; index++) {
            sortedArray[index] = toSortArray[index];
        }
        int leftIndex = low;
        int rightIndex = mid + 1;
        for (int k = low; k <= high; k++) {
            System.out.println(leftIndex + " " + rightIndex + " " + k);
            if (leftIndex > mid) {
                toSortArray[k] = sortedArray[rightIndex++];
            } else if (rightIndex > high) {
                toSortArray[k] = sortedArray[leftIndex++];
            } else if (sortedArray[leftIndex] < sortedArray[rightIndex]) {
                toSortArray[k] = sortedArray[leftIndex++];
            } else {
                toSortArray[k] = sortedArray[rightIndex++];
            }
        }
    }

 


Time Complexity: n log n

No comments:

Post a Comment

Search 24 Bytes

Loading...