package com.leecode.Sort;

import java.util.Arrays;

public class MergeSort {

//合并函数

void mergearray(int a[], int first, int mid, int last, int temp[])

{

int i = first, j = mid + 1;

int m = mid, n = last;

int k = 0;

while (i <= m && j <= n)

{

if (a[i] <= a[j])

temp[k++] = a[i++];

else

temp[k++] = a[j++];

}

//到这一步骤说明i或者j已到达子序列的末尾，没有加入的数字直接添加到辅助数组后边

while (i <= m)

temp[k++] = a[i++];

while (j <= n)

temp[k++] = a[j++];

for (i = 0; i < k; i++)

a[first + i] = temp[i];

}

//递归分割

void mergesort(int a[], int first, int last, int[] temp){

if(first<last){

int mid=(first+last)/2;

mergesort(a,first,mid,temp);//左边已排好顺序

mergesort(a,mid+1,last,temp);//右边已排好顺序

mergearray(a,first,mid,last,temp);//合并

}

}

boolean MergeSort(int a[], int n)

{

int[] p = new int[n];

mergesort(a, 0, n - 1, p);

return true;

}

public static void main(String[] args) {

int[] arr={3,1,4,6,1,2,52,0,1};

int n=arr.length;

MergeSort mergeSort=new MergeSort();

mergeSort.MergeSort(arr,n);

System.out.println(Arrays.toString(arr));

}

}