Merge Sort

Methodology

1. Split the array into the smallest subarrays, and each contains only 1 element
2. Merge 2 subarrays into 1 subarray
3. Repeat it until all the subarrays are merged

There are top-down and bottom-up methods

Time Complexity

Average Case

O(n log n)

Worst Case

O(n log n)

Space Complexity

Auxiliary Space

O(n)

Algorithm

public void MergeSort(int[] data, int front, int end) {
    if (front >= end) return;

    int mid = (front + end) / 2;
    MergeSort(data, front, mid);
    MergeSort(data, mid, end);
    Merge(data, front, mid, end);
}

public void Merge(int[] data, int front, int mid, int end) {
    int[] temp = new int[end-front];
    int i = front, j = mid+1;
    int k = 0;
    while(i < mid || j < end) {
        if(i < mid && (data[i] < data[j] || j >= end)) {
            temp[k++] = data[i++];
        } else  {
            temp[k++] = data[j++];
        }
    }

    // copy temp into data
    for(int i=0;i<temp.length;i++) data[front+i] = temp[i];
}