package Week08;

import java.util.Arrays;

public class MergeSort {

public int[] mergeSort(int[] arr){

mergeSort(arr,0,arr.length-1);

return arr;

}

private void mergeSort(int[] arr, int begin, int end) {

if (begin>=end) return;

int mid = (begin+end) >> 1;

mergeSort(arr,begin,mid);

mergeSort(arr,mid+1,end);

merge(arr,begin,mid,end);

}

private void merge(int[] arr, int left, int mid, int right) {

int[] temp = new int[right-left+1];

int i=left,j=mid+1;

int k=0;

while (i<=mid && j<=right){

temp[k++] = arr[i]<arr[j] ? arr[i++] : arr[j++];

}

while (i<=mid) temp[k++] = arr[i++];

while (j<=right) temp[k++] = arr[j++];

//copy from temp to arr

// for (int p=0;p<temp.length;p++){

// arr[left+p] = temp[p];

// }

System.arraycopy(temp,0,arr,left,temp.length);

}

private void swap(int[] arr, int i, int j) {

if (i==j) return;

arr[i] = (arr[i] + arr[j]) - (arr[j] = arr[i]);

}

}

class Test31 {

public static void main(String[] args) {

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

MergeSort sort = new MergeSort();

int[] ans = sort.mergeSort(arr);

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

}

}