Lecture
The merge sorting algorithm was proposed by the forefather of modern computers - John von Neumann. The method itself is stable , that is, it does not change the elements of the same value in the list.
The principle of "divide and conquer" is the basis of merge sorting. The list is divided into equal or almost equal parts, each of which is sorted separately. After that, the already ordered parts merge together. This process can be described in several details as follows:
The main MergeSort subroutine recursively splits and sorts an array, and Merge is responsible for its merging. So you can write the pseudocode of the main subroutine:
one 2 3 four five 6 7 eight 9 ten eleven | Subroutine MergeSort (A, first, last) { // A is an array // first, last - the numbers of the first and last elements, respectively If first <last then { Calling MergeSort (A, first, (first + last) / 2) // sorting the left side Calling MergeSort (A, (first + last) / 2 + 1, last) // sorting the right side Call Merge (A, first, last) // merge two parts } } |
This subroutine is executed only if the number of the first element is less than the number of the last one. As already mentioned, from the MergeSort subroutine, the Merge subroutine is called, which performs a merge operation. We turn to the consideration of the latter.
Merge's job is to form an ordered result array by merging two smaller sorted arrays as well. Here is the pseudocode of this subroutine:
one 2 3 four five 6 7 eight 9 ten eleven 12 13 14 15 sixteen 17 18 nineteen 20 21 | Subroutine Merge (A, first, last) { // start, final - the numbers of the first elements of the left and right parts // mas is an array, middle is the number of the middle element middle = (first + last) / 2 // calculation of the middle element start = first // start of the left side final = middle + 1 // start of the right side Cycle j = first to last execute // execute from beginning to end If ((start <= middle) and ((final> last) or (A [start] <A [final]))) then { mas [j] = A [start] increase start by 1 } Otherwise { mas [j] = A [final] increase final by 1 } Loop j = first to last execute // return the result to the list A [j] = mas [j] } |
Let us analyze the merge sort algorithm using the following example. There is an unordered sequence of numbers: 2, 6, 7, 1, 3, 5, 0, 4. After splitting this sequence into single arrays, the sorting merge process (in ascending order) will look like this:
The array was divided into single arrays, which the algorithm merges in pairs until one array is obtained, all the elements of which stand in their positions.
one 2 3 four five 6 7 eight 9 ten eleven 12 13 14 15 sixteen 17 18 nineteen 20 21 22 23 24 25 26 27 28 29 thirty 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | #include "stdafx.h" #include <iostream> using namespace std; // function that merges arrays void Merge (int * A, int first, int last) { int middle, start, final, j; int * mas = new int [100]; middle = (first + last) / 2; // calculate the middle element start = first; // start of the left side final = middle + 1; // start of the right side for (j = first; j <= last; j ++) // execute from beginning to end if ((start <= middle) && ((final> last) || (A [start] <A [final]))) { mas [j] = A [start]; start ++; } else { mas [j] = A [final]; final ++; } // return the result to the list for (j = first; j <= last; j ++) A [j] = mas [j]; delete [] mas; }; // recursive sorting procedure void MergeSort (int * A, int first, int last) { { if (first <last) { MergeSort (A, first, (first + last) / 2); // sort the left side MergeSort (A, (first + last) / 2 + 1, last); // sort the right side Merge (A, first, last); // merge two parts } } }; // main function void main () { setlocale (LC_ALL, "Rus"); int i, n; int * A = new int [100]; cout << "Array size>"; cin >> n; for (i = 1; i <= n; i ++) {cout << i << "element>"; cin >> A [i];} MergeSort (A, 1, n); // call the sorting procedure cout << "Ordered array:"; // output ordered array for (i = 1; i <= n; i ++) cout << A [i] << ""; delete [] A; system ("pause >> void"); } |
one 2 3 four five 6 7 eight 9 ten eleven 12 13 14 15 sixteen 17 18 nineteen 20 21 22 23 24 25 26 27 28 29 thirty 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 | program Sort_Marge; uses crt; type massiv = array [1..100] of integer; var n, i: integer; A: massiv; {procedure merging arrays} procedure Merge (var A: massiv; first, last: integer); var middle, start, final, j: integer; mas: massiv; begin middle: = (first + last) div 2; {calculation of the average element} start: = first; {beginning of the left side} final: = middle + 1; {beginning of the right side} for j: = first to last do {execute from beginning to end} if (start <= middle) and ((final> last) or (A [start] <A [final])) then begin mas [j]: = A [start]; inc (start); end else begin mas [j]: = A [final]; inc (final); end; {return result to array} for j: = first to last do A [j]: = mas [j]; end; {recursive sorting procedure} procedure MergeSort (var A: massiv; first, last: integer); begin if first <last then begin MergeSort (A, first, (first + last) div 2); {sorting the left side} MergeSort (A, (first + last) div 2 + 1, last); {sorting the right side} Merge (A, first, last); {merging of two parts} end; end; {main program block} begin clrscr; write ('array size>'); readln (n); for i: = 1 to n do begin write (i, 'element>'); read (A [i]); end; MergeSort (A, 1, n); {calling the sorting procedure} write ('Ordered array:'); {output sorted array} for i: = 1 to n do write (A [i], ''); readkey; end. |
The disadvantage of merge sorting is the use of additional memory. But when working with files or lists that are accessed only sequentially, it is very convenient to use this method. Also, the advantages of the algorithm include its stability and a good speed O (n * logn).
Comments
To leave a comment
Algorithms
Terms: Algorithms