First consider how to merge two ordered sequences. This is very simple. Just compare the first number of the two sequence and take the smaller one first. After taking it, delete the number in the corresponding sequence. Then compare them. If one of the columns is empty, just take out the data of the other column one by one.
Copy the code code as follows:
View Code
//Merge ordered arrays a[] and b[] into c[]
void MemeryArray(int a[], int n, int b[], int m, int c[])
{
int i, j, k;
i = j = k = 0;
while (i < n && j < m)
{
if (a[i] < b[j])
c[k++] = a[i++];
else
c[k++] = b[j++];
}
while (i < n)
c[k++] = a[i++];
while (j < m)
c[k++] = b[j++];
}
It can be seen that the efficiency of merging ordered sequence is relatively high and can reach O(n).
After solving the above problem of merging ordered sequences, let's look at merge sort. The basic idea is to divide the array into two groups A and B. If the data in these two groups are all ordered, then it can be easily These two sets of data are sorted. How to keep the data in these two groups in order?
Groups A and B can be divided into two groups. By analogy, when the separated group has only one data, it can be considered that the group has reached order, and then the two adjacent groups can be merged. In this way, merge sorting is completed by first decomposing the array recursively and then merging the array.
Copy the code code as follows:
View Code
//Will merge two ordered sequence a[first...mid] and a[mid...last].
void mergearray(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
while (i <= m && j <= n)
{
if (a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (i = 0; i < k; i++)
a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last, int temp[])
{
if (first < last)
{
int mid = (first + last) / 2;
mergesort(a, first, mid, temp); //Left side is sorted
mergesort(a, mid + 1, last, temp); //The right side is sorted
mergearray(a, first, mid, last, temp); //Merge the two ordered arrays
}
}
bool MergeSort(int a[], int n)
{
int *p = new int[n];
if (p == NULL)
return false;
mergesort(a, 0, n - 1, p);
delete[] p;
return true;
}
The efficiency of merge sort is relatively high. Assume the length of the sequence is N. It takes logN steps to divide the sequence into decimal sequences. Each step is a process of merging the ordered sequence. The time complexity can be recorded as O(N), so The total is O(N*logN). Because merge sort operates on adjacent data every time, several sorting methods of merge sort (quick sort, merge sort, Hill sort, heap sort) in O(N*logN) are also relatively efficient.