[Algorithm] 합병정렬 Merge Sort

김정민·2024년 3월 13일

algorithm

💡 합병정렬 Merge Sort

평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법

하나의 리스트를 반으로 분할하고 분할된 부분을 정렬하고 다시 합하여 전체를 정렬

🔑 단계

분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.

정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.

결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.

💎 소스

public class Main {
  public static void main(String[] args) {
    Solution solution = new Solution();
    SimpleDateFormat sdf1 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:ms");

// list 초기화 (10만 개의 양수)
    int[] list = new int[100000];
    Random random = new Random();
    for (int i = 0; i < list.length; i++) {
      list[i] = Math.abs(random.nextInt()); // 음수가 아닌 값 생성
    }


    Date now = new Date();
    String start = sdf1.format(now);
    int[] result = solution.solution(list);

    Date now2 = new Date();
    String end = sdf1.format(now2);


    System.out.println(start);
    System.out.println(end);

    System.out.println((now2.getTime() - now.getTime()) / 1000.0 + "초");

    // 결과 출력
    for (int i = 0; i < result.length; i++) {
      System.out.print(result[i]);
    }
  }
}

class Solution {
  public int[] solution(int[] numList) {

    int size = numList.length - 1;
    mergeSort(numList, 0, size);
    return numList;
  }

  void mergeSort(int[] numList, int left, int right) {

    int mid = 0;

    if (left < right) {
      // (left+right)/2 오버플로우 해결하기 위한 방법
      mid = left + (right - left) / 2;
      mergeSort(numList, left, mid);
      mergeSort(numList, mid + 1, right);
      merge(numList, left, mid, right);
    }
  }

  void merge(int[] list, int left, int mid, int right) {
    int[] sorted = new int[list.length];
    int i, j, k, l;
    i = left;
    j = mid + 1;
    k = left;

    /* 분할 정렬된 list의 합병 */
    while (i <= mid && j <= right) {
      if (list[i] <= list[j])
        sorted[k++] = list[i++];
      else
        sorted[k++] = list[j++];
    }

    // 남아 있는 값들을 일괄 복사
    if (i > mid) {
      for (l = j; l <= right; l++)
        sorted[k++] = list[l];
    }
    // 남아 있는 값들을 일괄 복사
    else {
      for (l = i; l <= mid; l++)
        sorted[k++] = list[l];
    }

    // 배열 sorted[](임시 배열)의 리스트를 배열 list[]로 재복사
    for (l = left; l <= right; l++)
      System.arraycopy(sorted, left, list, left, right - left + 1);
  }
}