Merge Sort

Merge Sort

/** merge method **/
	 public int[] merge(int[] array1, int[] array2) {
	        int[] combined = new int[array1.length + array2.length];
	        int index = 0;
	        int i = 0;
	        int j = 0;
	        while (i < array1.length && j < array2.length) {
	            if (array1[i] < array2[j]) {
	                combined[index] = array1[i];
	                index++;
	                i++;
	            } else {
	                combined[index] = array2[j];
	                index++;
	                j++;
	            }
	        }
	        while (i < array1.length) {
	            combined[index] = array1[i];
	            index++;
	            i++;
	        }
	        while (j < array2.length) {
	            combined[index] = array2[j];
	            index++;
	            j++;
	        } 
	        return combined;
	    }
	 
	 /** merge sort method **/
	// 1. recursive 2. using a merge method at the end
	public int [] mergeSort(int[] array) {
		if(array.length == 1) return array;
		
		int midIndex = array.length / 2;
		
		int[] left = mergeSort(Arrays.copyOfRange(array, 0, midIndex));
		int[] right = mergeSort(Arrays.copyOfRange(array, midIndex, array.length));
		
		return merge(left, right);
	}

Main

MergeSort me = new MergeSort();
		//int[] array1 = {1,3,7,8};
	    //int[] array2 = {2,4,5,6};
	    //System.out.println( Arrays.toString( me.merge(array1, array2) ) );
		
		int [] array = {1, 7, 3, 2};
		int [] array_new = me.mergeSort(array);
		System.out.println(Arrays.toString(array_new));

• break down : O(log n)....배열을 아이템이 하나가 될 때까지 계속해서 반으로 쪼갠다. 이 작업을 재귀로 수행.
• merging : O(n) ...... 다시 합침
• merge sort : O(n log n)