You get a bonus - 1 coin for daily activity. Now you have 1 coin

Merge sort

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:

  1. the array is recursively split in half, and each of the halves is divided until the size of the next subarray becomes equal to one;
  2. then an operation of the algorithm, called merge, is performed. Two unit arrays merge into a common result array, with a smaller element selected from each (ascending sort) and written to the free left cell of the result array. Then from the two resulting arrays, a third common sorted array is assembled, and so on. If one of the arrays ends, the elements of the other are added to the assembled array;
  3. at the end of the merge operation, the elements are overwritten from the resulting array to the original one.

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:

  Merge sort

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.

C ++ program code:

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");
}

Pascal program code:

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).

created: 2014-11-30
updated: 2021-03-13
132548



Rating 9 of 10. count vote: 2
Are you satisfied?:



Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Algorithms

Terms: Algorithms