logo

TechCodeview

マージソート - データ構造とアルゴリズムのチュートリアル

マージソート は、次のソート アルゴリズムです。 分割統治 アプローチ。これは、入力配列をより小さいサブ配列に再帰的に分割し、それらのサブ配列をソートしてから、それらをマージしてソートされた配列を取得することによって機能します。

簡単に言えば、次のようなプロセスであると言えます。 マージソート これは、配列を 2 つの半分に分割し、それぞれの半分を並べ替えてから、並べ替えられた半分を結合し直すことです。このプロセスは、配列全体がソートされるまで繰り返されます。



マージ-ソートアルゴリズム-(1)

マージソートアルゴリズム

マージソートはどのように機能しますか?

マージ ソートは、効率性と安定性で知られる人気のある並べ替えアルゴリズムです。それは次のとおりです 分割統治 指定された要素の配列を並べ替えるアプローチ。

ここでは、マージソートの仕組みを段階的に説明します。



  1. 分ける： 分割できなくなるまで、リストまたは配列を再帰的に 2 つの半分に分割します。
  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(配列, 中間 + 1, 終了);  マージ(配列、開始、中間、終了); } // ユーティリティ関数 // 配列を出力する関数 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 
// 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# 
// 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 
// 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+ parseInt((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) これは、大規模なデータセットでも良好なパフォーマンスを発揮することを意味します。
  • 実装が簡単: 分割統治のアプローチは簡単です。

マージソートの欠点:

  • 空間の複雑さ: マージソートでは、ソートプロセス中にマージされたサブ配列を保存するために追加のメモリが必要です。
  • 所定の場所にありません: マージ ソートはインプレース ソート アルゴリズムではないため、ソートされたデータを保存するために追加のメモリが必要になります。これは、メモリ使用量が懸念されるアプリケーションでは不利になる可能性があります。

マージソートの用途:

  • 大規模なデータセットの並べ替え
  • 外部ソート (データセットが大きすぎてメモリに収まらない場合)
  • 反転カウント (配列内の反転の数をカウント)
  • 配列の中央値を求める

クイックリンク：

  • マージソートに関する最近の記事
  • 面接の質問と問題のトップソート
  • ソートアルゴリズムの練習問題
  • マージソートに関するクイズ