Easy Tutorial
❮ Android Tutorial Layoutinflater Css Percentage Calculation ❯

Merge Sort Implementation

Category Programming Techniques

Merge sort is an efficient sorting algorithm based on the merge operation. It is a very typical application of the divide and conquer method.

First, consider how to merge two sorted sequences. This is very simple; just compare the first number of the two sequences, take the smaller one first, and then delete that number from the corresponding sequence. Then compare again, if one sequence is empty, just take out the data of the other sequence in turn.

//Merge sorted arrays a[] and b[] into c[]
void MergeArrays(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 sorted sequences is relatively high, reaching O(n).

Having solved the problem of merging sorted sequences, let's look at merge sort. Its basic idea is to divide the array into two groups A and B. If the data within these two groups are sorted, then these two groups of data can be sorted conveniently. How to make the data within these two groups sorted?

You can further divide groups A and B into two groups each. And so on, when the divided group has only one data, it can be considered that the group is already sorted, and then merge the adjacent two groups. In this way, by first recursively decomposing the sequence and then merging the sequence, merge sort is completed.

//Merge two sorted sequences 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 sorted
        MergeSort(a, mid + 1, last, temp); //Right side sorted
        MergeArray(a, first, mid, last, temp); //Then merge the two sorted sequences
    }
}

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. Let the length of the sequence be N. It takes logN steps to divide the sequence into smaller sequences, and each step is a process of merging a sorted sequence. The time complexity can be recorded as O(N), so the total is O(NlogN). Because merge sort operates on adjacent data each time, it is also more efficient among the O(NlogN) sorting methods (quick sort, merge sort, shell sort, heap sort).

Test with 20,000 random data:

Test with 50,000 random data:

Test again with 200,000 random data:

Note: Some books allocate a temporary array when merging sorted sequences in mergearray(), but too many new operations can be very time-consuming. Therefore, a small change was made. Only one temporary array is new in MergeSort(). The following operations all share this one temporary array.

>

Author: MoreWindows

Original article: https://blog.csdn.net/morewindows/article/details/6678165

**Click to share notes

Cancel

-

-

-

❮ Android Tutorial Layoutinflater Css Percentage Calculation ❯