Merge Sort [Sort Integers II]

二刷
public class Solution {
    /**
     * @param A an integer array
     * @return void
     */
    public void sortIntegers2(int[] A) {
        // Write your code here
        if (A == null || A.length <= 1) return;
        int[] copy = A.clone();
        sort(A, copy, 0, A.length - 1);
    }
   
    //Given a range [left, right]
    private void sort(int[] A, int[] copy, int left, int right) {
        if (left == right) return;
        int mid = (left + right) / 2;
        sort(A, copy, left, mid);
        sort(A, copy, mid + 1, right);
        merge(A, copy, left, mid, right);
    }
   
    private void merge(int[] A, int[] copy, int left, int mid, int right) {
        int leftCurr = left;
        int rightCurr = mid+ 1;
        int curr = left;
        while (leftCurr <= mid && rightCurr <= right) {
            if (copy[leftCurr] < copy[rightCurr]) {
                A[curr] = copy[leftCurr++];
            } else {
                A[curr] = copy[rightCurr++];
            }
            curr++;
        }
        while (leftCurr <= mid) {
            A[curr++] = copy[leftCurr++];
        }
        while (rightCurr <= right) {
            A[curr++] = copy[rightCurr++];
        }
        System.arraycopy(A, left, copy, left, right - left + 1);
    }
}

TestCase:

public static void main(String[] args) {

MergeSort solution = new MergeSort();

//test cases to cover all the possible situations

int[] array = null;

array = solution.mergeSort(array);

System.out.println(Arrays.toString(array));

array = new int[0];

array = solution.mergeSort(array);

System.out.println(Arrays.toString(array));

array = new int[] {1, 2, 3, 4};

array = solution.mergeSort(array);

System.out.println(Arrays.toString(array));

array = new int[] {4, 3, 2, 1};

array = solution.mergeSort(array);

System.out.println(Arrays.toString(array));

array = new int[] {2, 4, 1, 5, 3};

array = solution.mergeSort(array);

System.out.println(Arrays.toString(array));

Integer a = 10;

System.out.println(a);

}

MergeSort for ArrayList
(Unchecked)

public class Solution {

public static List<Integer> mergeSort(List<Integer> array) {

if (array == null || array.size() <= 1) return array;

return mergeSort(array, 0, array.size() - 1);

}

private List<Integer> mergeSort(List<Integer> array, int left, int right) {

if (left == right) {

List<Integer> result = new ArrayList<>();

result.add(array.get(left));

return result;

}

int mid = (left + right) / 2;

List<Integer> leftResult = mergeSort(array, left, mid);

List<Integer> rightResult = mergeSort(array, mid + 1, right);

return merge(leftResult, rightResult);

}

private List<Integer> mergeSort(List<Integer> leftResult, List<Integer> rightResult) {

int left = 0, right = 0;

List<Integer> result = new ArrayList<>();

while (left < leftResult.size() && right < rightResult.size()) {

if (leftResult.get(left) < rightResult.get(right)) {

result.add(leftResult.get(left++));

} else {

result.add(rightResult.get(right++));

}

}

while (left < leftResult.size()) result.add(leftResult.get(left++));

while(right < rightResult.size()) result.add(rightResult.get(right++));

return result;

}

}

一刷
public class Solution {
    /**
     * @param A an integer array
     * @return void
     */
    //Merge Sort
    public void sortIntegers2(int[] A) {
        // Write your code here
        if (A == null || A.length == 0) {
            return;
        }
        int[] temp = new int[A.length];
        mergeSort(A, 0, A.length - 1, temp);
    }
    private void mergeSort(int[] A, int start, int end, int[] temp) {
        if (start >= end) {
            return;
        }
        mergeSort(A, start, (start + end) / 2, temp);
        mergeSort(A, (start + end) / 2 + 1, end, temp);
        merge(A, start, end, temp);
    }
    private void merge(int[] A, int start, int end, int[] temp) {
     
        int mid = (start + end) / 2;
        int leftIndex = start;
        int rightIndex = mid + 1;
        int index = leftIndex;
        while (leftIndex <= mid && rightIndex <= end) {
            if (A[leftIndex] <= A[rightIndex]) {
                temp[index++] = A[leftIndex++];
            } else {
                temp[index++] = A[rightIndex++];
            }
        }
        while (leftIndex <= mid) {
            temp[index++] = A[leftIndex++];
        }
        while (rightIndex <= end) {
            temp[index++] = A[rightIndex++];
        }
        for (int i = start; i <= end; i++) {
            A[i] = temp[i];
        }
     
    }
}