MergeSortSolution.java

package kxi.rpc.test.basic;

class MergeSortSolution {

    private static void merge(int arr[], int left, int mid, int right) {
        int leftCount = mid - left + 1;
        int rightCount = right - mid;

        int leftArr[] = new int[leftCount];
        int rightArr[] = new int[rightCount];

        for (int i = 0; i < leftCount; ++i) {
            leftArr[i] = arr[left + i];
        }

        for (int j = 0; j < rightCount; ++j) {
            rightArr[j] = arr[mid + 1 + j];
        }

        int leftPoint = 0, rightPoint = 0;

        int point = left;
        while (leftPoint < leftCount && rightPoint < rightCount) {
            if (leftArr[leftPoint] <= rightArr[rightPoint]) {
                arr[point] = leftArr[leftPoint];
                leftPoint++;
            } else {
                arr[point] = rightArr[rightPoint];
                rightPoint++;
            }
            point++;
        }

        while (leftPoint < leftCount) {
            arr[point] = leftArr[leftPoint];
            leftPoint++;
            point++;
        }

        while (rightPoint < rightCount) {
            arr[point] = rightArr[rightPoint];
            rightPoint++;
            point++;
        }
    }

    public static void sort(int arr[], int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;

            sort(arr, left, mid);
            sort(arr, mid + 1, right);

            merge(arr, left, mid, right);
        }
    }
}

QuickSortSolution.java

package kxi.rpc.test.basic;

class QuickSortSolution {

    private static int partition(int arr[], int low, int high) {
        int pivot = arr[high];
        int i = (low - 1);
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }

        swap(arr, i + 1, high);
        return i + 1;
    }

    private static void swap(int arr[], int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void sort(int arr[], int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);
            sort(arr, low, pi - 1);
            sort(arr, pi + 1, high);
        }
    }
}