병합정렬

참고 : https://blog.naver.com/rlarjsdn529/222283896613

[Java] 합병정렬(Merge Sort) - 자바 / 그림설명 및 소스코드

import java.util.Scanner;

public class Main {
	public static void main(String args[]) {
		Scanner in = new Scanner(System.in);
		
		int n = in.nextInt();
		int arr[] = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = in.nextInt();
		}
		
		new Main().solution(n, arr);
		for (int i = 0; i < n; i++) {
			System.out.print(arr[i] + " ");
		}
		
	}
	
	public int[] solution(int n, int[] arr) {
		return mergeSort(arr, 0, n-1);
	}
	
	public int[] mergeSort(int[] arr, int start, int end) {
		if (start < end) {
			int mid = (start+end) / 2;
			mergeSort(arr, start, mid);
			mergeSort(arr, mid+1, end);
			merge(arr, start, mid, end);
		}
		
		return arr;
	}
	
	public void merge(int[] arr, int start, int mid, int end) {
		int[] tmp = new int[arr.length];
		
		int resultIndex = start;
		
		int leftIndex = start;
		int rightIndex = mid+1;
		
		while (leftIndex <= mid && rightIndex <= end) {
			int leftValue = arr[leftIndex];
			int rightValue = arr[rightIndex];
			
			if (leftValue < rightValue) {
				tmp[resultIndex++] = leftValue;
				leftIndex++;
			} else {
				tmp[resultIndex++] = rightValue;
				rightIndex++;
			}
		}
		
		// 남은것 넣어주기
		while (leftIndex <= mid) {
			tmp[resultIndex++] = arr[leftIndex++];
		} 
		while (rightIndex <= end) {
			tmp[resultIndex++] = arr[rightIndex++];;
		}
		
		for (int i = start; i <= end; i++) {
			arr[i] = tmp[i];
		}
	}
}