首页 > 代码库 > Merge Sort

Merge Sort

Good for array and linked list. Stable Sort.

Time Complexity: Best, Average, Worst => O(nlogn);

Space Complexity: O(n), in-place merge sort makes it very complicated.

public static void main(String[] args)    {        Random r = new Random();                int[] a = new int[]{r.nextInt(100), r.nextInt(100), r.nextInt(100),r.nextInt(100),r.nextInt(100),r.nextInt(100),r.nextInt(100),r.nextInt(100),r.nextInt(100),r.nextInt(100),r.nextInt(100)};        int[] aCopy1 = Arrays.copyOf(a, a.length);        int[] aCopy2 = Arrays.copyOf(a, a.length);        mergeSort1(aCopy1);        mergeSort2(aCopy2);        System.out.println(Arrays.toString(a));        System.out.println(Arrays.toString(aCopy1));                System.out.println(Arrays.toString(aCopy2));            }        private static void mergeSort1(int[] a)    {                        TopDownSplitMerge(a, 0, a.length, new int[a.length]);    }        //[begin,end)    private static void TopDownSplitMerge(int[] a, int iBegin, int iEnd, int[] helper)    {        if(iEnd-iBegin<2)            return;        int iMid = (iBegin + iEnd)/2;        TopDownSplitMerge(a, iBegin, iMid, helper);        TopDownSplitMerge(a, iMid, iEnd, helper);                //merge to helper array        //left half a[iBegin:iMid-1]        //right half a[iMid:iEnd-1]        int iLeft = iBegin;        int iRight = iMid;        for(int j=iBegin;j<iEnd;++j)        {            if(iLeft<iMid && (iRight>=iEnd || a[iLeft]<a[iRight]))            {                helper[j] = a[iLeft];                ++iLeft;            }            else            {                helper[j] = a[iRight];                ++iRight;            }        }                //copy values from helper array to original array.        for(int j = iBegin;j<iEnd;++j)        {            a[j] = helper[j];        }    }        private static void mergeSort2(int[] a)    {                        BottomUpMerge(a, a.length, new int[a.length]);    }        // Make successively longer sorted runs of length 2, 4, 8, 16... until whole array is sorted.    private static void BottomUpMerge(int[] a, int length, int[] helper)    {        for(int width = 1;width<length;width *=2)        {            for(int i = 0;i<length;i+=width*2)            {                //for each iteration, merge the range [i, i+2*width-1]                //left half: a[i: i+width-1]                //right half:a[i+width:i+2*width-1]                int iLeft = i;                int iMid = Math.min(i+width, length);                int iRight = iMid;                int iEnd = Math.min(i+2*width, length);                for(int j = iLeft; j<iEnd; ++j)                {                    if(iLeft<iMid && (iRight>=iEnd || a[iLeft]<a[iRight]))                    {                        helper[j] = a[iLeft];                        ++iLeft;                    }                    else                    {                        helper[j] = a[iRight];                        ++iRight;                    }                }            }                        //copy values from helper array to original array.            for(int j = 0;j<length;++j)            {                a[j] = helper[j];            }        }    }

 

Merge Sort