[ACE] Merge Sort Analysis

MergeSort

---

Divide and Conquer

Divide and Conquer is a general algorithm design paradigm:
Divide: divide the input data S in two disjoint subsets S1 and S2
Recur: solve the subproblems associated with S1 and S2
Conquer: combine the solutions for S1 and S2 into a solution for S
Merge-Sort and Quick-Sort both use divide and conquer method.

MergeSort

Merge-sort on an input sequence S with n elements consists of three steps:
• Divide: partition S into two sequences S1 and S2 of about n/2 elements each
• Recur: recursively sort S1 and S2
• Conquer: merge S1 and S2 into a unique sorted sequence
We first think about “conquer” step, to merge halves of an array, we need to traversal every element, so the runtime is O(n)
Implementation:

public static void recMergeSort(int [] arr, int [] workSpace, int l, int r){
    if(l == r){
        return;
    }else{
        int m = (l + r) / 2;
        recMergeSort(arr, workSpace, l, m);
        recMergeSort(arr, workSpace, m+1, r);
        merge(arr, workSpace, l, m+1, r);
        }
    }

It is a general implementation, as for Java, i write a code for its implementation and testing.

public class MergeSort {

    public static void main(String[] args) {
        int [] a = {5, 2, 4, 7, 1, 3, 2, 6};
        recMergeSort(a, 0, a.length-1);
        for(int i: a){
            System.out.println(i);
        }
    }
    public static void merge(int a[], int start, int mid, int end){
        int [] temp = new int [end-start+1];
        int i = start;
        int j = mid + 1;
        int k = 0;

        while(i <= mid && j <= end){
            if(a[i] < a[j]){
                temp[k++] = a[i++];
            }else{
                temp[k++] = a[j++];
            }
        }

        while(i <= mid){
            temp[k++] = a[i++];
        }

        while(j <= end){
            temp[k++] = a[j++];
        }

        for(i = 0; i < k; i++){
            a[start+i] = temp[i];
        }

        temp = null;
    }

    public static void recMergeSort(int [] a, int start, int end){
        if(a == null || start >= end){
            return;
        }

        int mid = (start + end)/2;
        recMergeSort(a, start, mid);
        recMergeSort(a, mid+1, end);

        merge(a, start, mid, end);
    }
}

After implement the mergesort, we should analysis the algorithm. What we do to analysis is use a merge-sort tree. Because it is obvious that the tree would be a perfect binary tree.

• The height h of the merge-sort tree is O(log n)
• The overall amount of work done at all the nodes at depth i is O(n)
• Thus, the total running time of merge-sort is O(n log n)

Using merge sort seems a good sorting algorithm and it is a fast sorting method for arrays. Good for sorting data in external memory- because works with adjacent indices in the array(data access is sequential)
However, it is not so good with lists: relies on constant time access to the middle of the sequence. For lists, you should traversal from the first element to get the middle element.

Stability?

It depends, depends on the implement method. It can be stable or unstable according to the comparsion(one equation sign). For the java code above, it is unstable.