归并排序

归并排序的算法是分治法的一个范例

Like QuickSort, Merge Sort is a Divide and Conquer algorithm.它被分成两半，调用自己来分两半，最后归并两半。merge()功能用于合并两半。The merge (arr,l,m,r)是关键的处理arr[l...m]和arr[m+1,r]被存储并合并两个子数组成为一个。

接下来是代码思想：

MergeSort(arr[],l,r)
If r>l:
    1.Find the middle point to divide the array into two halves: 
        middle m = (l+r)/2
    2.Call mergeSort for first half:
        Call mergeSort(arr,l,m)
    3.Call mergeSort for second half:
        Call mergeSort(arr,m+1,r)
    4.Merge the two halves sorted in step 2 and 3:
        Call merge(arr,l,m,r)

下面的流程图展示了完成一个merge排序的处理流程{38,27,43,3,9,82,10}。我们可以发现这个数组被递归分割成两部分知道大小变成1，一旦size到达1，merge处理流程合并生效，开始归并数组直到整个数组完成。

import java.util.Arrays;

public class mergSort {

    public static void main(String[] args)
    {
            int[] array = {5,2,3,7,9,10};

            //sort(array,0,array.length-1);
            sort(array,0,array.length-1);
            System.out.println(Arrays.toString(array));
    }


    public static void sort(int[] array,int l,int r)
    {
        if(l<r)
        {
            int mid = (l+r)/2;

            sort(array,l,mid);

            sort(array,mid+1,r);

            merge(array,l,mid,r);
        }


    }



    public static void merge(int[] array, int l, int m, int r)
    {
        int n1 = m-l+1;
        int n2 = r-m;

        //create two temp arrays

        int L[] = new int[n1];
        int R[] = new int[n2];

        for(int i=0;i<n1;i++)
        {
            L[i] = array[l+i];
        }

        for(int j=0;j<n2;j++)
        {
            R[j] = array[m+1+j];
        }


        //merge two array
        int i=0, j =0;
        int index = l;

        while((i<n1)&&(j<n2))
        {
            if(L[i]<=R[j])
            {
                array[index] = L[i];

                i++;
            }
            else
            {
                array[index] = R[j];

                j++;
            }
            index++;

        }

        while(i<n1)
        {
            array[index] = L[i];
            index++;
            i++;
        }

        while(j<n2)
        {
            array[index] = R[j];
            index++;
            j++;

        }



    }

}

Time Complexity:

T(n) = 2T(n/2) + O(n)

n*log2N