병합 정렬

병합 정렬은 재귀 용법을 활용한 정렬 알고리즘이다.

 

1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.

2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.

3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

 

이 병합 정렬은 분할 정복의 알고리즘 기법입니다.

분할 정복은 문제를 부분 문제로 나누며 이때 나누어진 부분 문제는 중복되지 않아야 합니다.

이러한 부분 문제를 통해 상위 문제를 해결하는 방법이며 하향식 즉 아래에서부터 위로 해결하는 방식입니다.

 

 

 

자바 코드 

배열을 받아 분할한다.

public static List<Integer> split(List<Integer> data) {

		List<Integer> leftSplit = new ArrayList<Integer>();

		List<Integer> rightSplit = new ArrayList<Integer>();

		int medium = data.size() / 2;

		if (data.size() == 1)
			return data;

		for (Integer number : data) {
			if (leftSplit.size() == medium)
				break;
			leftSplit.add(number);
		}

		for (int i = medium; i < data.size(); i++) {
			rightSplit.add(data.get(i));
		}

		List<Integer> left = split(leftSplit);
		List<Integer> right = split(rightSplit);

		return merge(left, right);
	}

 

분할했다면 정렬 후 합병한다.

public static List<Integer> merge(List<Integer> left, List<Integer> right) {

		List<Integer> result = new ArrayList();

		int leftIndex = 0;
		int rightIndex = 0;

		// 두개 배열중 더 작은수를 찾아서 새로운 배열에 넣는다.

		// case 1 : 두개의 분열된 배열에 값이 존재한경우
		while (left.size() > leftIndex && right.size() > rightIndex) {

			if (left.get(leftIndex) < right.get(rightIndex)) {
				result.add(left.get(leftIndex));
				leftIndex++;
			} else {
				result.add(right.get(rightIndex));
				rightIndex++;
			}
		}

		// left배열에만 데이터가 남은경우
		while (left.size() > leftIndex) {

			result.add(left.get(leftIndex));
			leftIndex++;
		}
		
		// right 배열에만 데이터가 남은경우
		while (right.size() > rightIndex) {

			result.add(right.get(rightIndex));
			leftIndex++;
		}

		return result;

	}

 

파이썬 코드는 다음과 같다.

 

def split (data):
	if(len(data) <=1):
		return data

  medium = int(len(data)/2)
  left = split(data[:medium])
  right = split(data[medium:)]
  
  return merge(left,right)
  
  
  
  def merge(left,right):
  merged = list()
  left_point,right_point = 0,0
  
  while len(left) > left_point and len(right) > right_point;
 	 if left[left_point] > right[right_point]:
      merged.append(right[right_point])
      right_point +=1
 	 else :
       merged.append(left[left_point])
      left_point +=1
      
  while len(left)>left_point:
     merged.append(left[left_point])
      left_point +=1
      
   while len(right)>right_point:
   merged.append(right[right_point])
      right_point +=1
      
    return merged

 

 

참고적으로 시간 복잡도를 구해본다면 해당 배열을 분할할 때 이진트리 형태로 깊어지고

해당 레벨에서 n만큼 연산이 일어나므로

대략적으로 O(N logN)이라고 할 수 있다