자료구조 - 병합정렬

병합 정렬이란 하나의 리스트를 두 개의 균등한 크기로 분할하는데 더 이상 분할되지 않을 때까지 한다.

 

그 다음 분할된 리스트 2개를 비교하여 정렬한 다음 하나의 리스트로 병합하여 정렬하는 방식이다. 

 

예를 들어 {8, 2, 3, 7, 1, 5, 4, 6} 이라는 배열이 있을 때 다음 그림과 같은 과정을 통해 정렬된다.

 

기존 배열

 

 

 

하나의 배열을 두 개의 배열로 분할한다.

 

 

 

또 각각의 배열은 두 개의 배열로 분할된다.

 

 

 

각각의 배열이 더 이상 나눠지지 않을 때까지 분할한다.

 

 

그리고 각 배열에 인접한 배열끼리 비교하여 오름차순으로 정렬한다.

 

 

 

비교하여 정렬한 배열은 병합한 후 인접한 배열끼리 비교하여 병합하는 과정을 반복한다.

 

 

 

계속 반복

 

 

이렇게 해서 정렬이 완성된다.

 

 

▼ 병합 정렬 코드

import java.io.*;
import java.util.*;

public class Main {
	
	public static void MergeSort(int arr[],int left, int right)
	{
		int mid;
		if(left<right)
		{
			mid = (right+left)/2;
			MergeSort(arr, left, mid);
			MergeSort(arr,mid+1,right);
			Merge(arr,left,mid,right);
		}
	}
	
	public static void Merge(int arr[],int left, int mid, int right)
	{
		int tmp[]= new int[right+1];
		int leftIndex=left;
		int rightIndex=mid+1;
		int sortedIndex=left;
		
		while(leftIndex <= mid && rightIndex <= right) {
			if(arr[leftIndex]<=arr[rightIndex]){
				tmp[sortedIndex++]=arr[leftIndex++];
			}
			else
				tmp[sortedIndex++]=arr[rightIndex++];	
		}
		if(leftIndex>mid)
		{
			for(int i=rightIndex;i<=right;i++)
				tmp[sortedIndex++]=arr[i];
		}
		else {
			for(int i=leftIndex;i<=mid;i++)
				tmp[sortedIndex++]=arr[i];
		}
		for(int i=left;i<=right;i++)
			arr[i]=tmp[i];
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int arr[] = {8,2,3,7,1,5,4,6};
		
		System.out.print("정렬 전 배열 : ");
		for(int val:arr)
			System.out.print(val+" ");
		
		MergeSort(arr,0,7);
		
		System.out.println();
		
		System.out.print("정렬 된 배열 : ");
		for(int val:arr)
			System.out.print(val+" ");
	}
}

 

 

실행결과