Algorithm

Merge Sort

orioncsy 2022. 10. 11. 10:08
import java.util.*;

public class Solution { 
	public int[] mergeSort(int[] arr) {
		// TODO :
    //재귀로 구현
    if(arr.length==1) return arr;
    int half=arr.length/2;
    int arr1[]=Arrays.copyOf(arr, half);
    int arr2[]=Arrays.copyOfRange(arr, half, arr.length);
    arr1=mergeSort(arr1);
    arr2=mergeSort(arr2);
    int j=0, k=0;
    for(int i=0; i<arr.length;i++){
      if(j<arr1.length && k<arr2.length){
        if(arr1[j]<arr2[k]) arr[i]=arr1[j++];
        else arr[i]=arr2[k++];
      }
      else if(j>=arr1.length) arr[i]=arr2[k++];
      else if(k>=arr2.length) arr[i]=arr1[j++];
    }
    return arr;
	}
}