I den här artikeln kommer vi att diskutera algoritmen för sammanslagning. Slå samman sortering är sorteringstekniken som följer skilje-och-härska-metoden. Den här artikeln kommer att vara mycket användbar och intressant för studenter eftersom de kan möta sammanslagningssortering som en fråga i sina undersökningar. I kodnings- eller tekniska intervjuer för mjukvaruingenjörer är sorteringsalgoritmer många frågade. Så det är viktigt att diskutera ämnet.
Slå samman sortering liknar algoritmen för snabbsortering eftersom den använder dividera och erövra-metoden för att sortera elementen. Det är en av de mest populära och effektiva sorteringsalgoritmerna. Den delar upp den givna listan i två lika stora halvor, kallar sig för de två halvorna och slår sedan samman de två sorterade halvorna. Vi måste definiera sammanfoga() funktion för att utföra sammanslagningen.
Underlistorna delas om och om igen i halvor tills listan inte kan delas upp ytterligare. Sedan kombinerar vi paret med ett elementlistor till listor med två element, och sorterar dem i processen. De sorterade tvåelementsparen slås samman till fyraelementslistorna, och så vidare tills vi får den sorterade listan.
Låt oss nu se algoritmen för sammanslagningssortering.
Algoritm
I följande algoritm, arr är den givna arrayen, be är startelementet, och slutet är det sista elementet i arrayen.
MERGE_SORT(arr, beg, end) if beg <end 2 set mid="(beg" + end) merge_sort(arr, beg, mid) 1, merge (arr, mid, end of if merge_sort < pre> <p>The important part of the merge sort is the <strong>MERGE</strong> function. This function performs the merging of two sorted sub-arrays that are <strong>A[beg…mid]</strong> and <strong>A[mid+1…end]</strong> , to build one sorted array <strong>A[beg…end]</strong> . So, the inputs of the <strong>MERGE</strong> function are <strong>A[], beg, mid,</strong> and <strong>end</strong> .</p> <p>The implementation of the <strong>MERGE</strong> function is given as follows -</p> <pre> /* Function to merge the subarrays of a[] */ void merge(int a[], int beg, int mid, int end) { int i, j, k; int n1 = mid - beg + 1; int n2 = end - mid; int LeftArray[n1], RightArray[n2]; //temporary arrays /* copy data to temp arrays */ for (int i = 0; i <n1; 1 i++) leftarray[i]="a[beg" + i]; for (int j="0;" < n2; j++) rightarray[j]="a[mid" j]; i="0," * initial index of first sub-array second k="beg;" merged while (i n1 && n2) { if(leftarray[i] a[k]="LeftArray[i];" i++; } else j++; k++; (i<n1) (j<n2) pre> <h2>Working of Merge sort Algorithm</h2> <p>Now, let's see the working of merge sort Algorithm.</p> <p>To understand the working of the merge sort algorithm, let's take an unsorted array. It will be easier to understand the merge sort via an example.</p> <p>Let the elements of array are -</p> <img src="//techcodeview.com/img/ds-tutorial/79/merge-sort-algorithm.webp" alt="Merge sort"> <p>According to the merge sort, first divide the given array into two equal halves. Merge sort keeps dividing the list into equal parts until it cannot be further divided.</p> <p>As there are eight elements in the given array, so it is divided into two arrays of size 4.</p> <img src="//techcodeview.com/img/ds-tutorial/79/merge-sort-algorithm-2.webp" alt="Merge sort"> <p>Now, again divide these two arrays into halves. As they are of size 4, so divide them into new arrays of size 2.</p> <img src="//techcodeview.com/img/ds-tutorial/79/merge-sort-algorithm-3.webp" alt="Merge sort"> <p>Now, again divide these arrays to get the atomic value that cannot be further divided.</p> <img src="//techcodeview.com/img/ds-tutorial/79/merge-sort-algorithm-4.webp" alt="Merge sort"> <p>Now, combine them in the same manner they were broken.</p> <p>In combining, first compare the element of each array and then combine them into another array in sorted order.</p> <p>So, first compare 12 and 31, both are in sorted positions. Then compare 25 and 8, and in the list of two values, put 8 first followed by 25. Then compare 32 and 17, sort them and put 17 first followed by 32. After that, compare 40 and 42, and place them sequentially.</p> <img src="//techcodeview.com/img/ds-tutorial/79/merge-sort-algorithm-5.webp" alt="Merge sort"> <p>In the next iteration of combining, now compare the arrays with two data values and merge them into an array of found values in sorted order.</p> <img src="//techcodeview.com/img/ds-tutorial/79/merge-sort-algorithm-6.webp" alt="Merge sort"> <p>Now, there is a final merging of the arrays. After the final merging of above arrays, the array will look like -</p> <img src="//techcodeview.com/img/ds-tutorial/79/merge-sort-algorithm-7.webp" alt="Merge sort"> <p>Now, the array is completely sorted.</p> <h2>Merge sort complexity</h2> <p>Now, let's see the time complexity of merge sort in best case, average case, and in worst case. We will also see the space complexity of the merge sort.</p> <h3>1. Time Complexity</h3> <table class="table"> <tr> <th>Case</th> <th>Time Complexity</th> </tr> <tr> <td> <strong>Best Case</strong> </td> <td>O(n*logn)</td> </tr> <tr> <td> <strong>Average Case</strong> </td> <td>O(n*logn)</td> </tr> <tr> <td> <strong>Worst Case</strong> </td> <td>O(n*logn)</td> </tr> </table> <ul> <tr><td>Best Case Complexity -</td> It occurs when there is no sorting required, i.e. the array is already sorted. The best-case time complexity of merge sort is <strong>O(n*logn)</strong> . </tr><tr><td>Average Case Complexity -</td> It occurs when the array elements are in jumbled order that is not properly ascending and not properly descending. The average case time complexity of merge sort is <strong>O(n*logn)</strong> . </tr><tr><td>Worst Case Complexity -</td> It occurs when the array elements are required to be sorted in reverse order. That means suppose you have to sort the array elements in ascending order, but its elements are in descending order. The worst-case time complexity of merge sort is <strong>O(n*logn)</strong> . </tr></ul> <h3>2. Space Complexity</h3> <table class="table"> <tr> <td> <strong>Space Complexity</strong> </td> <td>O(n)</td> </tr> <tr> <td> <strong>Stable</strong> </td> <td>YES</td> </tr> </table> <ul> <li>The space complexity of merge sort is O(n). It is because, in merge sort, an extra variable is required for swapping.</li> </ul> <h2>Implementation of merge sort</h2> <p>Now, let's see the programs of merge sort in different programming languages.</p> <p> <strong>Program:</strong> Write a program to implement merge sort in C language.</p> <pre> #include /* Function to merge the subarrays of a[] */ void merge(int a[], int beg, int mid, int end) { int i, j, k; int n1 = mid - beg + 1; int n2 = end - mid; int LeftArray[n1], RightArray[n2]; //temporary arrays /* copy data to temp arrays */ for (int i = 0; i <n1; 1 42 i++) leftarray[i]="a[beg" + i]; for (int j="0;" < n2; j++) rightarray[j]="a[mid" j]; i="0;" * initial index of first sub-array second k="beg;" merged while (i n1 && n2) { if(leftarray[i] a[k]="LeftArray[i];" i++; } else j++; k++; (i<n1) (j<n2) void mergesort(int a[], int beg, end) if (beg mid="(beg" 2; mergesort(a, mid); 1, end); merge(a, mid, function to print the array printarray(int n) i; n; printf('%d ', a[i]); printf('
'); main() a[]="{" 12, 31, 25, 8, 32, 17, 40, }; n="sizeof(a)" sizeof(a[0]); printf('before sorting elements are -
'); printarray(a, n); 0, 1); printf('after return 0; pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/79/merge-sort-algorithm-8.webp" alt="Merge sort"> <p> <strong>Program:</strong> Write a program to implement merge sort in C++ language.</p> <pre> #include using namespace std; /* Function to merge the subarrays of a[] */ void merge(int a[], int beg, int mid, int end) { int i, j, k; int n1 = mid - beg + 1; int n2 = end - mid; int LeftArray[n1], RightArray[n2]; //temporary arrays /* copy data to temp arrays */ for (int i = 0; i <n1; 1 41 i++) leftarray[i]="a[beg" + i]; for (int j="0;" < n2; j++) rightarray[j]="a[mid" j]; i="0;" * initial index of first sub-array second k="beg;" merged while (i n1 && n2) { if(leftarray[i] a[k]="LeftArray[i];" i++; } else j++; k++; (i<n1) (j<n2) void mergesort(int a[], int beg, end) if (beg mid="(beg" 2; mergesort(a, mid); 1, end); merge(a, mid, function to print the array printarray(int n) i; n; cout< <a[i]<<' '; main() a[]="{" 11, 30, 24, 7, 31, 16, 39, }; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting elements are -
'; printarray(a, n); 0, 1); cout<<'
after return 0; pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/79/merge-sort-algorithm-9.webp" alt="Merge sort"> <p> <strong>Program:</strong> Write a program to implement merge sort in Java.</p> <pre> class Merge { /* Function to merge the subarrays of a[] */ void merge(int a[], int beg, int mid, int end) { int i, j, k; int n1 = mid - beg + 1; int n2 = end - mid; /* temporary Arrays */ int LeftArray[] = new int[n1]; int RightArray[] = new int[n2]; /* copy data to temp arrays */ for (i = 0; i <n1; 1 41 i++) leftarray[i]="a[beg" + i]; for (j="0;" j < n2; j++) rightarray[j]="a[mid" j]; i="0;" * initial index of first sub-array second k="beg;" merged while (i n1 && n2) { if(leftarray[i] a[k]="LeftArray[i];" i++; } else j++; k++; (i<n1) (j<n2) void mergesort(int a[], int beg, end) if (beg mid="(beg" 2; mergesort(a, mid); 1, end); merge(a, mid, function to print the array printarray(int n) i; n; system.out.print(a[i] ' '); public static main(string args[]) a[]="{" 11, 30, 24, 7, 31, 16, 39, }; n="a.length;" merge m1="new" merge(); system.out.println('
before sorting elements are - m1.printarray(a, n); m1.mergesort(a, 0, 1); system.out.println('
after system.out.println(''); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/79/merge-sort-algorithm-10.webp" alt="Merge sort"> <p> <strong>Program:</strong> Write a program to implement merge sort in C#.</p> <pre> using System; class Merge { /* Function to merge the subarrays of a[] */ static void merge(int[] a, int beg, int mid, int end) { int i, j, k; int n1 = mid - beg + 1; int n2 = end - mid; //temporary arrays int[] LeftArray = new int [n1]; int[] RightArray = new int [n2]; /* copy data to temp arrays */ for (i = 0; i <n1; 1 40 i++) leftarray[i]="a[beg" + i]; for (j="0;" j < n2; j++) rightarray[j]="a[mid" j]; i="0;" * initial index of first sub-array second k="beg;" merged while (i n1 && n2) { if(leftarray[i] a[k]="LeftArray[i];" i++; } else j++; k++; (i<n1) (j<n2) static void mergesort(int[] a, int beg, end) if (beg mid="(beg" 2; mergesort(a, mid); 1, end); merge(a, mid, function to print the array printarray(int[] n) i; n; console.write(a[i] ' '); main() int[] a="{" 10, 29, 23, 6, 30, 15, 38, }; n="a.Length;" console.write('before sorting elements are - printarray(a, n); 0, 1); console.write('
after pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/79/merge-sort-algorithm-11.webp" alt="Merge sort"> <p> <strong>Program:</strong> Write a program to implement merge sort in PHP.</p> <pre> <?php /* Function to merge the subarrays of a[] */ function merge(&$a, $beg, $mid, $end) { $n1 = ($mid - $beg) + 1; $n2 = $end - $mid; /* temporary Arrays */ $LeftArray = array($n1); $RightArray = array($n2); /* copy data to temp arrays */ for ($i = 0; $i < $n1; $i++) $LeftArray[$i] = $a[$beg + $i]; for ($j = 0; $j < $n2; $j++) $RightArray[$j] = $a[$mid + 1 + $j]; $i = 0; /* initial index of first sub-array */ $j = 0; /* initial index of second sub-array */ $k = $beg; /* initial index of merged sub-array */ while ($i<$n1 && $j<$n2) { if($LeftArray[$i] <= $RightArray[$j]) { $a[$k] = $LeftArray[$i]; $i++; } else { $a[$k] = $RightArray[$j]; $j++; } $k++; } while ($i<$n1) { $a[$k] = $LeftArray[$i]; $i++; $k++; } while ($j<$n2) { $a[$k] = $RightArray[$j]; $j++; $k++; } } function mergeSort(&$a, $beg, $end) { if ($beg < $end) { $mid = (int)(($beg + $end) / 2); mergeSort($a, $beg, $mid); mergeSort($a, $mid + 1, $end); merge($a, $beg, $mid, $end); } } /* Function to print array elements */ function printArray($a, $n) { for($i = 0; $i < $n; $i++) { print_r($a[$i]); echo ' '; } } $a = array( 10, 29, 23, 6, 30, 15, 38, 40 ); $n = count($a); echo 'Before sorting array elements are - <br>'; printArray($a, $n); mergeSort($a, 0, $n - 1); echo ' <br> After sorting array elements are - <br>'; printArray($a, $n); ?> </pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/79/merge-sort-algorithm-12.webp" alt="Merge sort"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the Merge sort complexity, working, and implementation in different programming languages.</p> <hr></n1;></pre></n1;></pre></n1;></pre></n1;></pre></n1;></pre></end> Produktion:
Så det handlar om artikeln. Hoppas artikeln kommer att vara användbar och informativ för dig.
Den här artikeln var inte bara begränsad till algoritmen. Vi har också diskuterat Merge-sortens komplexitet, arbete och implementering i olika programmeringsspråk.