Merge Sort Template

public void sortIntegers2(int[] A) {
    // use a shared temp array, the extra memory is O(n) at least
    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;
    }
    int mid = start + (end - start) / 2;
    mergeSort(A, start, mid, temp);
    mergeSort(A, mid + 1, end, temp);
    merge(A, start, mid, end, temp);
}
private void merge(int[] A, int start, int mid, int end, int[] temp){
    int left = start;
    int right = mid + 1;
    int index = start;
    // merge two sorted subarrays in A to temp array
    while(left <= mid && right <= end){
        if(A[left] < A[right]){
            temp[index++] = A[left++];
        } else {
            temp[index++] = A[right++];
        }
    }
    while(left <= mid){
        temp[index++] = A[left++];
    }
    while(right <= mid){
        temp[index++] = A[right++];
    }
    // copy temp back to A
    for(index = start; index <= end; index++){
        A[index] = temp[index];
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s