Merge Sort

Merge Sort?

• Devide, Conquer, Combine의 원리를 활용한 정렬 방식

장점

• 시간복잡도가 좋음: O(nlogn)
  (Bubble, Insertion, Selection Sort의 O(n^2)보다 좋음)
  
• 안정 정렬: 같은 숫자라도 그 상대적인 위치가 유지되는 sort방식
• 따라서 대규모 데이터 세트에서 빠르게 sorting 가능

단점

• 공간복잡도에서 불리함: O(n)
  (merge한 array를 임시로 저장할 공간이 추가적으로 필요하므로 작은 데이터 세트에서 효율적이지 않음)
  
• 작은 데이터 세트에서 recursive 호출과 merge process에 대한 overhead 발생 우려

구현

package SortingAlgorithm;

import java.util.Arrays;
import java.util.Random;

public class MergeSort {

    public static void main(String[] args) {

        Random rand = new Random();

        int[] numbers = new int[10];
        for(int i=0; i<numbers.length; i++){
            numbers[i] = rand.nextInt(10); //bound: zero to million
        }

        System.out.println("Before MergeSort: ");
        printArray(numbers);

        mergeSort(numbers);

        System.out.println("\nAfter MergeSort: ");
        printArray(numbers);
    }

    private static void mergeSort(int[] inputArray){
        int inputLength = inputArray.length;

        //3. until one element (already sorted)
        if(inputLength < 2){
            return;
        }

        //1. devide in a half
        int midIndex = inputLength / 2;
        int[] leftHalf = new int[midIndex];
        int[] rightHalf = new int[inputLength - midIndex];

        for(int i=0; i<midIndex; i++){
            leftHalf[i] = inputArray[i];
        }
        for(int i=midIndex; i<inputLength; i++){
            rightHalf[i - midIndex] = inputArray[i];
        }

        //2. recursive call
        mergeSort(leftHalf);
        mergeSort(rightHalf);

        //4. merge
        merge(inputArray, leftHalf, rightHalf);
    }

    private static void merge(int[] inputArray, int[] leftHalf, int[] rightHalf){
        int leftSize = leftHalf.length;
        int rightSize = rightHalf.length;

        //iterator for each array
        int i=0, j=0, k=0;
        while (i<leftSize && j<rightSize){
            if(leftHalf[i] <= rightHalf[j]){ //compare each element
                inputArray[k] = leftHalf[i]; //and put smaller one into an organized array
                i++;
            }else{
                inputArray[k] = rightHalf[j];
                j++;
            }
            k++;
        }

        //for leftover
        while (i<leftSize){
            inputArray[k] = leftHalf[i];
            i++;
            k++;
        }
        while (j<rightSize){
            inputArray[k] = rightHalf[j];
            j++;
            k++;
        }

        //still remaining one
    }

    private static void printArray(int[] inputArray){

        System.out.println(Arrays.toString(inputArray));
    }

}

---

출처
https://www.youtube.com/watch?v=bOk35XmHPKs
https://www.youtube.com/watch?v=3j0SWDX4AtU