Merge sorting is one of the basic informatics algorithms formulated back in 1945 by the great mathematician John von Neumann. Participating in the Manhattan Project, Neumann was faced with the need to efficiently process huge amounts of data. The method developed by him used the principle of "divide and conquer", which allowed to significantly reduce the time required for work.
Principle and use of the algorithm
The merge sorting method is used in sorting problems of structures that have ordered access to elements, for example, arrays, lists, streams.
During processing, the initial data block is split into small components, up to one element, which in essence is already a sorted list. Then reassembly takes place in the correct order.
Sorting an array of a certain length requires an additional memory area of a similar size, in which a sorted array is assembled in parts.
The method can be used to organize any comparable data types, such as numbers or strings.
Merging Sorted Plots
To understand the algorithm, we will start its analysis from the end - from the mechanism of merging sorted blocks.
Imagine that we have two sorted arrays of numbers in any way that need to be combined with each other so that the sorting is not violated. For simplicity, we will arrange the numbers in ascending order.
Elementary example: both arrays consist of one element each.
int[] arr1 = {31}; int[] arr2 = {18};
To merge them, you need to take the zero element of the first array (do not forget that the numbering starts from zero) and the zero element of the second array. These are, respectively, 31 and 18. By the sorting condition, the number 18 should go first, since it is less. Just arrange the numbers in the correct order:
int[] result = {18, 31};
Let's turn to a more complicated example, in which each array consists of several elements:
int[] arr1 = {2, 17, 19, 45}; int[] arr2 = {5, 6, 21, 30};
The merge algorithm will consist in comparing the smaller elements sequentially and placing them in the resulting array in the correct order. To track the current indexes, we introduce two variables - index1 and index2. Initially, we equate them to zero, since the arrays are sorted, and the smallest elements are at the beginning.
int index1 = 0; int index2 = 0;
We will describe in steps the whole merger process:
- We take from the arr1 array the element with index1, and from the arr2 array - with index2.
- Compare, select the smallest of them and put in the resulting array.
- Increase the current index of the smaller element by 1.
- We continue from the first step.
At the first turn, the situation will look like this:
index1 = 0; index2 = 0; arr1[0] = 2; arr2[0] = 5; arr1[0] < arr2[0]; index1++; result[0] = arr1[0];
In the second round:
index1 = 1; index2 = 0; arr1[1] = 17; arr2[0] = 5; arr1[1] > arr2[0]; index2++; result[1] = arr2[0];
On the third:
index1 = 1; index2 = 1; arr1[1] = 17; arr2[1] = 6; arr1[1] > arr2[1]; index2++; result[2] = arr2[1];
And so on, until you end up with a fully sorted resulting array: {2, 5, 6, 17, 21, 19, 30, 45}.
Certain difficulties can arise if arrays with different lengths merge. What if one of the current indices reaches the last element, and there are still members in the second array?
int[] arr1 = {1, 4}; int[] arr2 = {2, 5, 6, 7, 9};
The variable index1 has reached the value 2, however the array arr1 does not have an element with such an index. Everything is simple here: it is enough to transfer the remaining elements of the second array to the resulting one, preserving their order.
result = {1, 2, 4, 5, 6, 7, 9};
This situation indicates to us the need to compare the current check index with the length of the merged array.
Scheme for merging ordered sequences (A and B) of different lengths:
- If the length of both sequences is greater than 0, compare A [0] and B [0] and move the smaller one to the buffer.
- If the length of one of the sequences is 0, take the remaining elements of the second sequence and, without changing their order, transfer to the end of the buffer.
Second stage implementation
An example of combining two sorted arrays in the Java language is given below.
int[] a1 = new int[] {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int[] a2 = new int[] {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int[] a3 = new int[a1.length + a2.length]; int i=0, j=0; for (int k=0; k<a3.length; k++) { if (i > a1.length-1) { int a = a2[j]; a3[k] = a; j++; } else if (j > a2.length-1) { int a = a1[i]; a3[k] = a; i++; } else if (a1[i] < a2[j]) { int a = a1[i]; a3[k] = a; i++; } else { int b = a2[j]; a3[k] = b; j++; } }
Here:
- a1 and a2 are the original sorted arrays that need to be combined;
- a3 is the final array;
- i and j are the indices of the current elements for arrays a1 and a2.
The first and second if conditions ensure that indexes do not go beyond the size of the array. The third and fourth blocks of conditions, respectively, are moved to the resulting array of the smaller element.
Divide and rule
So we learned how to combine sorted collections of values. We can say that the second part of the merge sorting algorithm - directly merging - is already parsed.
However, it is also necessary to understand how to get from a source unsorted array of numbers to several sorted ones that can be merged.
Consider the first stage of the algorithm and learn how to separate arrays.
There is nothing complicated about it - the initial list of values is divided in half, then each part is also bifurcated, and so on until very small blocks are obtained.
The length of such minimal elements can be equal to one, that is, they can themselves be a sorted array, however this is not a prerequisite. The size of the block is determined in advance, and any suitable sorting algorithm that works effectively with small-sized arrays (for example, quick sort or insertion sorting) can be used to organize it.
It looks as follows.
The resulting blocks, consisting of 1-2 elements, are very simple to arrange.
After that, it is necessary to combine the already sorted small arrays in pairs, preserving the order of the members, which we have already learned to do.
Phase One Implementation
Recursive partitioning of an array is shown below.
void mergeSort(T a[], long start, long finish) { long split; if (start < finish) { split = (start + finish)/2; mergeSort(a, start, split); mergeSort(a, split+1, finish); merge(a, start, split, finish); } }
What happens in this code:
- The mergeSort function gets the original array
a and the left and right borders of the section to be sorted (start and finish indices). - If the length of this section is greater than one (
start < finish ), then it is divided into two parts (by the split index), and each of them is recursively sorted. - In the recursive function call for the left side, the initial parcel index and the
split index are passed. For the right one, respectively, the beginning will be (split + 1) , and the end will be the last index of the source section. - The
merge function receives two ordered sequences ( a[start]...a[split] and a[split+1]...a[finish] ) and merges them while preserving the sort order.
The mechanics of the merge function are discussed above.
General algorithm scheme
The merge array sorting method consists of two large steps:
- Divide the unsorted source array into small parts.
- Collect them in pairs, following the sorting rule.
The big and difficult task here is divided into many simple ones, which are successively solved, leading to the desired result.
Evaluation of the method
The time complexity of merge sorting is determined by the height of the algorithm partition tree and is equal to the number of elements in the array (n) multiplied by its logarithm (log n). Such an estimate is called logarithmic.
This is both a virtue and a disadvantage of the method. Its operating time does not change even in the worst case, when the original array is sorted in reverse order. However, when processing completely sorted data, the algorithm does not provide a time gain.
It is important to note the memory overhead when using the merge sort method. They are equal to the size of the original collection. In this additionally selected area, a sorted array is assembled from pieces.
Algorithm implementation
Pascal merge sort is shown below.
Procedure MergeSort(name: string; var f: text); Var a1,a2,s,i,j,kol,tmp: integer; f1,f2: text; b: boolean; Begin kol:=0; Assign(f,name); Reset(f); While not EOF(f) do begin read(f,a1); inc(kol); End; Close(f); Assign(f1,'{ 1- }'); Assign(f2,'{ 2- }'); s:=1; While (s<kol) do begin Reset(f); Rewrite(f1); Rewrite(f2); For i:=1 to kol div 2 do begin Read(f,a1); Write(f1,a1,' '); End; If (kol div 2) mod s<>0 then begin tmp:=kol div 2; While tmp mod s<>0 do begin Read(f,a1); Write(f1,a1,' '); inc(tmp); End; End; While not EOF(f) do begin Read(f,a2); Write(f2,a2,' '); End; Close(f); Close(f1); Close(f2); Rewrite(f); Reset(f1); Reset(f2); Read(f1,a1); Read(f2,a2); While (not EOF(f1)) and (not EOF(f2)) do begin i:=0; j:=0; b:=true; While (b) and (not EOF(f1)) and (not EOF(f2)) do begin If (a1<a2) then begin Write(f,a1,' '); Read(f1,a1); inc(i); End else begin Write(f,a2,' '); Read(f2,a2); inc(j); End; If (i=s) or (j=s) then b:=false; End; If not b then begin While (i<s) and (not EOF(f1)) do begin Write(f,a1,' '); Read(f1,a1); inc(i); End; While (j<s) and (not EOF(f2)) do begin Write(f,a2,' '); Read(f2,a2); inc(j); End; End; End; While not EOF(f1) do begin tmp:=a1; Read(f1,a1); If not EOF(f1) then Write(f,tmp,' ') else Write(f,tmp); End; While not EOF(f2) do begin tmp:=a2; Read(f2,a2); If not EOF(f2) then Write(f,tmp,' ') else Write(f,tmp); End; Close(f); Close(f1); Close(f2); s:=s*2; End; Erase(f1); Erase(f2); End;
Visually, the operation of the algorithm looks like this (above is an unordered sequence, below is an ordered sequence).
External data sorting
Very often there is a need to sort some data located in the external memory of the computer. In some cases, they are impressive in size and cannot be placed in RAM to facilitate access to them. For such cases, external sorting methods are used.
The need to access external media degrades the temporary processing efficiency.
The complexity of the work lies in the fact that the algorithm at each moment in time can have access to only one element of the data stream. And in this case, one of the best results is shown by the merge sort method, which can compare the elements of two files sequentially one after another.
Reading data from an external source, its processing and writing to the final file are carried out in ordered blocks (series). According to the method of working with the size of ordered series, two types of sorting are distinguished: simple and natural merging.
Simple merge
With a simple merge, the length of the series is fixed.
So, in the original unsorted file, all series consist of one element. After the first step, the size increases to two. Next - 4, 8, 16 and so on.
It works as follows:
- The source file (f) is divided into two auxiliary files - f1, f2.
- They merge again into one file (f), but at the same time all the elements are compared in pairs and form pairs already. The series size at this step becomes equal to two.
- Repeat step 1.
- Step 2 is repeated, but the already ordered deuces merge, forming sorted fours.
- The cycle continues, accompanied by an increase in the series at each turn, until the entire file is sorted.
How to understand that external sorting by simple merge is complete?
- the new length of the series (after merging) is not less than the total number of elements;
- there is only one episode left;
- helper file f2 remained empty.
The disadvantages of a simple merge are the following: since the length of the series is fixed at each merge pass, partially ordered data will be processed as long as it is absolutely chaotic.
Natural fusion
This method does not limit the length of the series, but selects the maximum possible.
Sort Algorithm:
- Reading the source sequence from file f begins. The first item received is written to file f1.
- If the next record satisfies the sorting condition, it is written there, if not, then to the second auxiliary file f2.
- Thus, all the records of the source file are distributed, and in f1 an ordered sequence is formed, which determines the current size of the series.
- Files f1 and f2 merge.
- The cycle repeats.
Due to the fixed size of the series, it is necessary to designate the end of the sequence with a special symbol. Therefore, when merging, the number of comparisons increases. In addition, the size of one of the auxiliary files may approach the size of the original.
On average, the natural merge method works more efficiently than a simple merge in external sorting.
Algorithm Features
When comparing two identical values, the method preserves their original order, that is, it is stable.
The sorting process can be very successfully divided into several threads.
The video clearly demonstrates the operation of the merge array sorting algorithm.