logo

TechCodeview

병합 정렬 – 데이터 구조 및 알고리즘 자습서

병합 정렬 다음을 따르는 정렬 알고리즘입니다. 분할 정복 접근하다. 입력 배열을 더 작은 하위 배열로 재귀적으로 나누고 해당 하위 배열을 정렬한 다음 다시 병합하여 정렬된 배열을 얻는 방식으로 작동합니다.

쉽게 말하면 진행과정이라고 할 수 있습니다. 병합 정렬 배열을 두 부분으로 나누고 각 부분을 정렬한 다음 정렬된 부분을 다시 병합하는 것입니다. 이 과정은 전체 배열이 정렬될 때까지 반복됩니다.

병합 정렬 알고리즘-(1)

병합 정렬 알고리즘



숫자로 백만

병합 정렬은 어떻게 작동하나요?

병합 정렬은 효율성과 안정성으로 널리 알려진 정렬 알고리즘입니다. 그것은 다음과 같습니다 분할 정복 주어진 요소 배열을 정렬하는 접근 방식입니다.

병합 정렬의 작동 방식을 단계별로 설명하면 다음과 같습니다.

  1. 나누다: 목록이나 배열을 더 이상 나눌 수 없을 때까지 두 부분으로 재귀적으로 나눕니다.
  2. 정복하다: 각 하위 배열은 병합 정렬 알고리즘을 사용하여 개별적으로 정렬됩니다.
  3. 병합: 정렬된 하위 배열은 정렬된 순서대로 다시 병합됩니다. 두 하위 배열의 모든 요소가 병합될 때까지 프로세스가 계속됩니다.

병합 정렬 그림:

배열이나 목록을 정렬해 봅시다 [38, 27, 43, 10] 병합 정렬 사용

위 예제의 작업을 살펴보겠습니다.

나누다:

  • [38, 27, 43, 10] 으로 나누어진다 [38, 27 ] 그리고 [43, 10] .
  • [38, 27] 로 나누어진다 [38] 그리고 [27] .
  • [43, 10] 으로 나누어진다 [43] 그리고 [10] .

정복하다:

  • [38] 이미 정렬되어 있습니다.
  • [27] 이미 정렬되어 있습니다.
  • [43] 이미 정렬되어 있습니다.
  • [10] 이미 정렬되어 있습니다.

병합:

  • 병합 [38] 그리고 [27] 얻기 위해 [27, 38] .
  • 병합 [43] 그리고 [10] 얻기 위해 [10.43] .
  • 병합 [27, 38] 그리고 [10.43] 최종 정렬 목록을 얻으려면 [10, 27, 38, 43]

따라서 정렬된 목록은 다음과 같습니다. [10, 27, 38, 43] .

추천 연습 시도해 보세요!

병합 정렬 구현:

C++ 
// C++ program for Merge Sort #include  using namespace std; // Merges two subarrays of array[]. // First subarray is arr[begin..mid] // Second subarray is arr[mid+1..end] void merge(int array[], int const left, int const mid,  int const right) {  int const subArrayOne = mid - left + 1;  int const subArrayTwo = right - mid;  // Create temp arrays  auto *leftArray = new int[subArrayOne],  *rightArray = new int[subArrayTwo];  // Copy data to temp arrays leftArray[] and rightArray[]  for (auto i = 0; i < subArrayOne; i++)  leftArray[i] = array[left + i];  for (auto j = 0; j < subArrayTwo; j++)  rightArray[j] = array[mid + 1 + j];  auto indexOfSubArrayOne = 0, indexOfSubArrayTwo = 0;  int indexOfMergedArray = left;  // Merge the temp arrays back into array[left..right]  while (indexOfSubArrayOne < subArrayOne  && indexOfSubArrayTwo < subArrayTwo) {  if (leftArray[indexOfSubArrayOne]  <= rightArray[indexOfSubArrayTwo]) {  array[indexOfMergedArray]  = leftArray[indexOfSubArrayOne];  indexOfSubArrayOne++;  }  else {  array[indexOfMergedArray]  = rightArray[indexOfSubArrayTwo];  indexOfSubArrayTwo++;  }  indexOfMergedArray++;  }  // Copy the remaining elements of  // left[], if there are any  while (indexOfSubArrayOne < subArrayOne) {  array[indexOfMergedArray]  = leftArray[indexOfSubArrayOne];  indexOfSubArrayOne++;  indexOfMergedArray++;  }  // Copy the remaining elements of  // right[], if there are any  while (indexOfSubArrayTwo < subArrayTwo) {  array[indexOfMergedArray]  = rightArray[indexOfSubArrayTwo];  indexOfSubArrayTwo++;  indexOfMergedArray++;  }  delete[] leftArray;  delete[] rightArray; } // begin is for left index and end is right index // of the sub-array of arr to be sorted void mergeSort(int array[], int const begin, int const end) {  if (begin>= 끝) 반환;  int mid = 시작 + (끝 - 시작) / 2;  mergeSort(배열, 시작, 중간);  mergeSort(배열, mid + 1, end);  merge(배열, 시작, 중간, 끝); } // 유틸리티 함수 // 배열을 인쇄하는 함수 void printArray(int A[], int size) { for (int i = 0; i< size; i++)  cout << A[i] << ' ';  cout << endl; } // Driver code int main() {  int arr[] = { 12, 11, 13, 5, 6, 7 };  int arr_size = sizeof(arr) / sizeof(arr[0]);  cout << 'Given array is 
';  printArray(arr, arr_size);  mergeSort(arr, 0, arr_size - 1);  cout << '
Sorted array is 
';  printArray(arr, arr_size);  return 0; } // This code is contributed by Mayank Tyagi // This code was revised by Joshua Estes>
씨 
// C program for Merge Sort #include  #include  // Merges two subarrays of arr[]. // First subarray is arr[l..m] // Second subarray is arr[m+1..r] void merge(int arr[], int l, int m, int r) {  int i, j, k;  int n1 = m - l + 1;  int n2 = r - m;  // Create temp arrays  int L[n1], R[n2];  // Copy data to temp arrays L[] and R[]  for (i = 0; i < n1; i++)  L[i] = arr[l + i];  for (j = 0; j < n2; j++)  R[j] = arr[m + 1 + j];  // Merge the temp arrays back into arr[l..r  i = 0;  j = 0;  k = l;  while (i < n1 && j < n2) {  if (L[i] <= R[j]) {  arr[k] = L[i];  i++;  }  else {  arr[k] = R[j];  j++;  }  k++;  }  // Copy the remaining elements of L[],  // if there are any  while (i < n1) {  arr[k] = L[i];  i++;  k++;  }  // Copy the remaining elements of R[],  // if there are any  while (j < n2) {  arr[k] = R[j];  j++;  k++;  } } // l is for left index and r is right index of the // sub-array of arr to be sorted void mergeSort(int arr[], int l, int r) {  if (l < r) {  int m = l + (r - l) / 2;  // Sort first and second halves  mergeSort(arr, l, m);  mergeSort(arr, m + 1, r);  merge(arr, l, m, r);  } } // Function to print an array void printArray(int A[], int size) {  int i;  for (i = 0; i < size; i++)  printf('%d ', A[i]);  printf('
'); } // Driver code int main() {  int arr[] = { 12, 11, 13, 5, 6, 7 };  int arr_size = sizeof(arr) / sizeof(arr[0]);  printf('Given array is 
');  printArray(arr, arr_size);  mergeSort(arr, 0, arr_size - 1);  printf('
Sorted array is 
');  printArray(arr, arr_size);  return 0; }>
자바 
// Java program for Merge Sort import java.io.*; class MergeSort {  // Merges two subarrays of arr[].  // First subarray is arr[l..m]  // Second subarray is arr[m+1..r]  void merge(int arr[], int l, int m, int r)  {  // Find sizes of two subarrays to be merged  int n1 = m - l + 1;  int n2 = r - m;  // Create temp arrays  int L[] = new int[n1];  int R[] = new int[n2];  // Copy data to temp arrays  for (int i = 0; i < n1; ++i)  L[i] = arr[l + i];  for (int j = 0; j < n2; ++j)  R[j] = arr[m + 1 + j];  // Merge the temp arrays  // Initial indices of first and second subarrays  int i = 0, j = 0;  // Initial index of merged subarray array  int k = l;  while (i < n1 && j < n2) {  if (L[i] <= R[j]) {  arr[k] = L[i];  i++;  }  else {  arr[k] = R[j];  j++;  }  k++;  }  // Copy remaining elements of L[] if any  while (i < n1) {  arr[k] = L[i];  i++;  k++;  }  // Copy remaining elements of R[] if any  while (j < n2) {  arr[k] = R[j];  j++;  k++;  }  }  // Main function that sorts arr[l..r] using  // merge()  void sort(int arr[], int l, int r)  {  if (l < r) {  // Find the middle point  int m = l + (r - l) / 2;  // Sort first and second halves  sort(arr, l, m);  sort(arr, m + 1, r);  // Merge the sorted halves  merge(arr, l, m, r);  }  }  // A utility function to print array of size n  static void printArray(int arr[])  {  int n = arr.length;  for (int i = 0; i < n; ++i)  System.out.print(arr[i] + ' ');  System.out.println();  }  // Driver code  public static void main(String args[])  {  int arr[] = { 12, 11, 13, 5, 6, 7 };  System.out.println('Given array is');  printArray(arr);  MergeSort ob = new MergeSort();  ob.sort(arr, 0, arr.length - 1);  System.out.println('
Sorted array is');  printArray(arr);  } } /* This code is contributed by Rajat Mishra */>
파이썬 
# Merges two subarrays of array[]. # First subarray is arr[left..mid] # Second subarray is arr[mid+1..right] def merge(array, left, mid, right): subArrayOne = mid - left + 1 subArrayTwo = right - mid # Create temp arrays leftArray = [0] * subArrayOne rightArray = [0] * subArrayTwo # Copy data to temp arrays leftArray[] and rightArray[] for i in range(subArrayOne): leftArray[i] = array[left + i] for j in range(subArrayTwo): rightArray[j] = array[mid + 1 + j] indexOfSubArrayOne = 0 # Initial index of first sub-array indexOfSubArrayTwo = 0 # Initial index of second sub-array indexOfMergedArray = left # Initial index of merged array # Merge the temp arrays back into array[left..right] while indexOfSubArrayOne < subArrayOne and indexOfSubArrayTwo < subArrayTwo: if leftArray[indexOfSubArrayOne] <= rightArray[indexOfSubArrayTwo]: array[indexOfMergedArray] = leftArray[indexOfSubArrayOne] indexOfSubArrayOne += 1 else: array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo] indexOfSubArrayTwo += 1 indexOfMergedArray += 1 # Copy the remaining elements of left[], if any while indexOfSubArrayOne < subArrayOne: array[indexOfMergedArray] = leftArray[indexOfSubArrayOne] indexOfSubArrayOne += 1 indexOfMergedArray += 1 # Copy the remaining elements of right[], if any while indexOfSubArrayTwo < subArrayTwo: array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo] indexOfSubArrayTwo += 1 indexOfMergedArray += 1 # begin is for left index and end is right index # of the sub-array of arr to be sorted def mergeSort(array, begin, end): if begin>= end: return mid = Begin + (end - Begin) // 2 mergeSort(array, Begin, mid) mergeSort(array, mid + 1, end) merge(array, Begin, mid, end) # 배열을 인쇄하는 함수 def printArray(array, size): for i in range(size): print(array[i], end=' ') print() # 드라이버 코드 if __name__ == '__main__': arr = [12 , 11, 13, 5, 6, 7] arr_size = len(arr) print('주어진 배열은') printArray(arr, arr_size) mergeSort(arr, 0, arr_size - 1) print('
정렬된 배열 is') printArray(arr, arr_size)>
씨# 
// C# program for Merge Sort using System; class MergeSort {  // Merges two subarrays of []arr.  // First subarray is arr[l..m]  // Second subarray is arr[m+1..r]  void merge(int[] arr, int l, int m, int r)  {  // Find sizes of two  // subarrays to be merged  int n1 = m - l + 1;  int n2 = r - m;  // Create temp arrays  int[] L = new int[n1];  int[] R = new int[n2];  int i, j;  // Copy data to temp arrays  for (i = 0; i < n1; ++i)  L[i] = arr[l + i];  for (j = 0; j < n2; ++j)  R[j] = arr[m + 1 + j];  // Merge the temp arrays  // Initial indexes of first  // and second subarrays  i = 0;  j = 0;  // Initial index of merged  // subarray array  int k = l;  while (i < n1 && j < n2) {  if (L[i] <= R[j]) {  arr[k] = L[i];  i++;  }  else {  arr[k] = R[j];  j++;  }  k++;  }  // Copy remaining elements  // of L[] if any  while (i < n1) {  arr[k] = L[i];  i++;  k++;  }  // Copy remaining elements  // of R[] if any  while (j < n2) {  arr[k] = R[j];  j++;  k++;  }  }  // Main function that  // sorts arr[l..r] using  // merge()  void sort(int[] arr, int l, int r)  {  if (l < r) {  // Find the middle point  int m = l + (r - l) / 2;  // Sort first and second halves  sort(arr, l, m);  sort(arr, m + 1, r);  // Merge the sorted halves  merge(arr, l, m, r);  }  }  // A utility function to  // print array of size n  static void printArray(int[] arr)  {  int n = arr.Length;  for (int i = 0; i < n; ++i)  Console.Write(arr[i] + ' ');  Console.WriteLine();  }  // Driver code  public static void Main(String[] args)  {  int[] arr = { 12, 11, 13, 5, 6, 7 };  Console.WriteLine('Given array is');  printArray(arr);  MergeSort ob = new MergeSort();  ob.sort(arr, 0, arr.Length - 1);  Console.WriteLine('
Sorted array is');  printArray(arr);  } } // This code is contributed by Princi Singh>
자바스크립트 
// JavaScript program for Merge Sort // Merges two subarrays of arr[]. // First subarray is arr[l..m] // Second subarray is arr[m+1..r] function merge(arr, l, m, r) {  var n1 = m - l + 1;  var n2 = r - m;  // Create temp arrays  var L = new Array(n1);   var R = new Array(n2);  // Copy data to temp arrays L[] and R[]  for (var i = 0; i < n1; i++)  L[i] = arr[l + i];  for (var j = 0; j < n2; j++)  R[j] = arr[m + 1 + j];  // Merge the temp arrays back into arr[l..r]  // Initial index of first subarray  var i = 0;  // Initial index of second subarray  var j = 0;  // Initial index of merged subarray  var k = l;  while (i < n1 && j < n2) {  if (L[i] <= R[j]) {  arr[k] = L[i];  i++;  }  else {  arr[k] = R[j];  j++;  }  k++;  }  // Copy the remaining elements of  // L[], if there are any  while (i < n1) {  arr[k] = L[i];  i++;  k++;  }  // Copy the remaining elements of  // R[], if there are any  while (j < n2) {  arr[k] = R[j];  j++;  k++;  } } // l is for left index and r is // right index of the sub-array // of arr to be sorted function mergeSort(arr,l, r){  if(l>=r){ 반환;  } var m =l+ parsInt((r-l)/2);  mergeSort(arr,l,m);  mergeSort(arr,m+1,r);  병합(arr,l,m,r); } // 배열을 인쇄하는 함수 function printArray( A, size) { for (var i = 0; i< size; i++)  console.log( A[i] + ' '); } var arr = [ 12, 11, 13, 5, 6, 7 ];  var arr_size = arr.length;  console.log( 'Given array is ');  printArray(arr, arr_size);  mergeSort(arr, 0, arr_size - 1);  console.log( 'Sorted array is ');  printArray(arr, arr_size); // This code is contributed by SoumikMondal>
PHP 
 /* PHP recursive program for Merge Sort */ // Merges two subarrays of arr[]. // First subarray is arr[l..m] // Second subarray is arr[m+1..r] function merge(&$arr, $l, $m, $r) { $n1 = $m - $l + 1; $n2 = $r - $m; // Create temp arrays $L = array(); $R = array(); // Copy data to temp arrays L[] and R[] for ($i = 0; $i < $n1; $i++) $L[$i] = $arr[$l + $i]; for ($j = 0; $j < $n2; $j++) $R[$j] = $arr[$m + 1 + $j]; // Merge the temp arrays back into arr[l..r] $i = 0; $j = 0; $k = $l; while ($i < $n1 && $j < $n2) { if ($L[$i] <= $R[$j]) { $arr[$k] = $L[$i]; $i++; } else { $arr[$k] = $R[$j]; $j++; } $k++; } // Copy the remaining elements of L[],  // if there are any while ($i < $n1) { $arr[$k] = $L[$i]; $i++; $k++; } // Copy the remaining elements of R[],  // if there are any while ($j < $n2) { $arr[$k] = $R[$j]; $j++; $k++; } } // l is for left index and r is right index of the // sub-array of arr to be sorted function mergeSort(&$arr, $l, $r) { if ($l < $r) { $m = $l + (int)(($r - $l) / 2); // Sort first and second halves mergeSort($arr, $l, $m); mergeSort($arr, $m + 1, $r); merge($arr, $l, $m, $r); } } // Function to print an array function printArray($A, $size) { for ($i = 0; $i < $size; $i++) echo $A[$i].' '; echo '
'; } // Driver code $arr = array(12, 11, 13, 5, 6, 7); $arr_size = sizeof($arr); echo 'Given array is 
'; printArray($arr, $arr_size); mergeSort($arr, 0, $arr_size - 1); echo '
Sorted array is 
'; printArray($arr, $arr_size); return 0; //This code is contributed by Susobhan Akhuli ?>>
산출 
Given array is 12 11 13 5 6 7 Sorted array is 5 6 7 11 12 13>

병합 정렬의 복잡성 분석:

시간 복잡도:

  • 최선의 경우: O(n log n), 배열이 이미 정렬되었거나 거의 정렬된 경우입니다.
  • 평균 사례: O(n log n), 배열이 무작위로 정렬된 경우.
  • 최악의 경우: O(n log n), 배열을 역순으로 정렬한 경우.

공간 복잡도: O(n), 병합 시 사용되는 임시 배열을 위한 추가 공간이 필요합니다.

병합 정렬의 장점:

  • 안정 : 병합 정렬은 안정적인 정렬 알고리즘입니다. 즉, 입력 배열에서 동일한 요소의 상대적 순서를 유지한다는 의미입니다.
  • 최악의 성능 보장: 병합 정렬의 최악의 경우 시간 복잡도는 다음과 같습니다. O(N logN) 이는 대규모 데이터 세트에서도 잘 작동한다는 것을 의미합니다.
  • 구현이 간단함: 분할 정복 접근법은 간단합니다.

병합 정렬의 단점:

  • 공간 복잡도: 병합 정렬에는 정렬 프로세스 중에 병합된 하위 배열을 저장하기 위한 추가 메모리가 필요합니다.
  • 제자리에 있지 않음: 병합 정렬은 내부 정렬 알고리즘이 아닙니다. 즉, 정렬된 데이터를 저장하려면 추가 메모리가 필요합니다. 이는 메모리 사용량이 문제가 되는 애플리케이션에서는 단점이 될 수 있습니다.

병합 정렬의 응용:

  • 대규모 데이터세트 정렬
  • 외부 정렬(데이터세트가 너무 커서 메모리에 맞지 않는 경우)
  • 반전 계산(배열의 반전 횟수 계산)
  • 배열의 중앙값 찾기

빠른 링크:

  • 병합 정렬에 관한 최근 기사
  • 상위 정렬 인터뷰 질문 및 문제
  • 정렬 알고리즘 연습 문제
  • 병합 정렬에 관한 퀴즈