Merge sort

Summary

This chapter introduces merge sort in sorting algorithm . The content includes ：
1.  Introduction to merging and sorting
2.  Description of merging and sorting
3.  The time complexity and stability of merging and sorting
4.  Merge sort implementation
4.1   Merge sort C Realization
4.2   Merge sort C++ Realization
4.3   Merge sort Java Realization

Reprint please indicate the source ： Merge sort - If the sky doesn't die - Blog Garden

---

For more sorting and algorithms, please refer to ： Data structure and algorithm series Catalog

Introduction to merging and sorting

To combine two ordered sequences into one , We call it " Merger ".
Merge sort (Merge Sort) Is to use the idea of merging to sort the sequence of numbers . According to the concrete implementation , Merge sort includes " From the top down " and " From bottom to top "2 Ways of planting .

1.  Sort up and down ： Divide the sequence to be sorted into several lengths of 1 The subsequence of , Then combine these two series ; We get a number of lengths 2 An ordered sequence of numbers , Then combine these two series ; We get a number of lengths 4 An ordered sequence of numbers , Combine them two again ; Merge directly into a sequence . In this way, we get the sorting result we want .( Refer to the picture below )

2.  Merge and sort from top to bottom ： It is associated with " From bottom to top " It is in the opposite direction in sorting . It basically includes 3 Step ：
① decompose -- Divide the current interval into two , That is, find the splitting point mid = (low + high)/2;
② solve -- Recursively for two subintervals a[low...mid] and a[mid+1...high] Merge and sort . The end condition of recursion is that the length of the subinterval is 1.
③ Merge -- The sorted two sub intervals a[low...mid] and a[mid+1...high] Merge into an ordered interval a[low...high].

The following picture clearly reflects " From bottom to top " and " From the top down " The difference between merging and sorting of .

Description of merging and sorting

Merge sort ( From the top down ) Code

/*
 *  Merge two adjacent ordered intervals in an array into one 
 *
 *  Parameter description ：
 *     a --  An array containing two ordered intervals 
 *     start --  The first 1 The starting address of an ordered interval .
 *     mid   --  The first 1 The end address of an ordered interval . Also the first 2 The starting address of an ordered interval .
 *     end   --  The first 2 The end address of an ordered interval .
 */
void merge(int a[], int start, int mid, int end)
{
    int *tmp = (int *)malloc((end-start+1)*sizeof(int));    // tmp Is summary 2 A temporary area in an orderly area 
    int i = start;            //  The first 1 Index of an ordered area 
    int j = mid + 1;        //  The first 2 Index of an ordered area 
    int k = 0;                //  Index of staging area 

    while(i <= mid && j <= end)
    {
        if (a[i] <= a[j])
            tmp[k++] = a[i++];
        else
            tmp[k++] = a[j++];
    }

    while(i <= mid)
        tmp[k++] = a[i++];

    while(j <= end)
        tmp[k++] = a[j++];

    //  The sorted elements , All integrated into the array a in .
    for (i = 0; i < k; i++)
        a[start + i] = tmp[i];

    free(tmp);
}

/*
 *  Merge sort ( From the top down )
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     start --  The starting address of the array 
 *     endi --  The end address of the array 
 */
void merge_sort_up2down(int a[], int start, int end)
{
    if(a==NULL || start >= end)
        return ;

    int mid = (end + start)/2;
    merge_sort_up2down(a, start, mid); //  Recursive sorting a[start...mid]
    merge_sort_up2down(a, mid+1, end); //  Recursive sorting a[mid+1...end]

    // a[start...mid]  and  a[mid...end] It's two ordered spaces ,
    //  Sort them into an ordered space a[start...end]
    merge(a, start, mid, end);
}

The merging and sorting from top to bottom is realized in a recursive way . Its principle is very simple , Here's the picture ：

adopt " Merge and sort from top to bottom " To the array {80,30,60,40,20,10,50,70} When sorting ：
1. Will array {80,30,60,40,20,10,50,70} As if by two ordered subarrays {80,30,60,40} and {20,10,50,70} form . Sort two subgroups in order .
2. Sub array {80,30,60,40} As if by two ordered subarrays {80,30} and {60,40} form .
    Sub array {20,10,50,70} As if by two ordered subarrays {20,10} and {50,70} form .
3. Sub array {80,30} As if by two ordered subarrays {80} and {30} form .
    Sub array {60,40} As if by two ordered subarrays {60} and {40} form .
    Sub array {20,10} As if by two ordered subarrays {20} and {10} form .
    Sub array {50,70} As if by two ordered subarrays {50} and {70} form .

Merge sort ( From bottom to top ) Code

/*
 *  An array a Do several mergers ： Array a The total length of is len, Divide it into several parts with a length of gap Subarray ;
 *              take " Every time 2 Adjacent subarrays "  Merge sort .
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     len --  Length of array 
 *     gap --  Length of subarray 
 */
void merge_groups(int a[], int len, int gap)
{
    int i;
    int twolen = 2 * gap;    //  The length of two adjacent subarrays 

    //  take " Every time 2 Adjacent subarrays "  Merge sort .
    for(i = 0; i+2*gap-1 < len; i+=(2*gap))
    {
        merge(a, i, i+gap-1, i+2*gap-1);
    }

    //  if  i+gap-1 < len-1, Then one of the remaining sub arrays is not paired .
    //  Merge the subarray into the sorted array .
    if ( i+gap-1 < len-1)
    {
        merge(a, i, i + gap - 1, len - 1);
    }
}

/*
 *  Merge sort ( From bottom to top )
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     len --  Length of array 
 */
void merge_sort_down2up(int a[], int len)
{
    int n;

    if (a==NULL || len<=0)
        return ;

    for(n = 1; n < len; n*=2)
        merge_groups(a, len, n);
}

The idea of merging and sorting from bottom to top coincides with " Sort up and down " contrary . Here's the picture ：

adopt " Sort up and down " To the array {80,30,60,40,20,10,50,70} When sorting ：
1. Will array {80,30,60,40,20,10,50,70} See as from 8 An ordered subarray {80},{30},{60},{40},{20},{10},{50} and {70} form .
2. Will this 8 Two ordered subsequences are merged . obtain 4 An ordered subtree column {30,80},{40,60},{10,20} and {50,70}.
3. Will this 4 Two ordered subsequences are merged . obtain 2 An ordered subtree column {30,40,60,80} and {10,20,50,70}.
4. Will this 2 Two ordered subsequences are merged . obtain 1 An ordered subtree column {10,20,30,40,50,60,70,80}.

The time complexity and stability of merging and sorting

Merge sort time complexity
The time complexity of merging and sorting is O(N*lgN).
Let's assume that the sequence being sorted has N Number . The time complexity of traversing a trip is O(N), How many times does it take to traverse ？
The form of merge sort is a binary tree , The number of times it needs to traverse is the depth of the binary tree , According to the of complete binary tree, we can conclude that its time complexity is O(N*lgN).

Merge sort stability
Merge sort is a stable algorithm , It satisfies the definition of stable algorithm .
Algorithm stability -- Let's assume that there exists in a sequence a[i]=a[j], If before sorting ,a[i] stay a[j] front ; And after sorting ,a[i] Still in a[j] front . Then the sorting algorithm is stable ！

Merge sort implementation

Here are three implementations of merge sorting ：C、C++ and Java. The principle and output results of these three implementations are the same , Each implementation includes " Merge and sort from top to bottom " and " Sort up and down " this 2 In the form of .
Merge sort C Realization
Implementation code (merge_sort.c)

/**
 *  Merge sort ：C  Language 
 *
 * @author skywang
 * @date 2014/03/12
 */

#include <stdio.h>
#include <stdlib.h>

//  The length of the array 
#define LENGTH(array) ( (sizeof(array)) / (sizeof(array[0])) )

/*
 *  Merge two adjacent ordered intervals in an array into one 
 *
 *  Parameter description ：
 *     a --  An array containing two ordered intervals 
 *     start --  The first 1 The starting address of an ordered interval .
 *     mid   --  The first 1 The end address of an ordered interval . Also the first 2 The starting address of an ordered interval .
 *     end   --  The first 2 The end address of an ordered interval .
 */
void merge(int a[], int start, int mid, int end)
{
    int *tmp = (int *)malloc((end-start+1)*sizeof(int));    // tmp Is summary 2 A temporary area in an orderly area 
    int i = start;            //  The first 1 Index of an ordered area 
    int j = mid + 1;        //  The first 2 Index of an ordered area 
    int k = 0;                //  Index of staging area 

    while(i <= mid && j <= end)
    {
        if (a[i] <= a[j])
            tmp[k++] = a[i++];
        else
            tmp[k++] = a[j++];
    }

    while(i <= mid)
        tmp[k++] = a[i++];

    while(j <= end)
        tmp[k++] = a[j++];

    //  The sorted elements , All integrated into the array a in .
    for (i = 0; i < k; i++)
        a[start + i] = tmp[i];

    free(tmp);
}

/*
 *  Merge sort ( From the top down )
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     start --  The starting address of the array 
 *     endi --  The end address of the array 
 */
void merge_sort_up2down(int a[], int start, int end)
{
    if(a==NULL || start >= end)
        return ;

    int mid = (end + start)/2;
    merge_sort_up2down(a, start, mid); //  Recursive sorting a[start...mid]
    merge_sort_up2down(a, mid+1, end); //  Recursive sorting a[mid+1...end]

    // a[start...mid]  and  a[mid...end] It's two ordered spaces ,
    //  Sort them into an ordered space a[start...end]
    merge(a, start, mid, end);
}


/*
 *  An array a Do several mergers ： Array a The total length of is len, Divide it into several parts with a length of gap Subarray ;
 *              take " Every time 2 Adjacent subarrays "  Merge sort .
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     len --  Length of array 
 *     gap --  Length of subarray 
 */
void merge_groups(int a[], int len, int gap)
{
    int i;
    int twolen = 2 * gap;    //  The length of two adjacent subarrays 

    //  take " Every time 2 Adjacent subarrays "  Merge sort .
    for(i = 0; i+2*gap-1 < len; i+=(2*gap))
    {
        merge(a, i, i+gap-1, i+2*gap-1);
    }

    //  if  i+gap-1 < len-1, Then one of the remaining sub arrays is not paired .
    //  Merge the subarray into the sorted array .
    if ( i+gap-1 < len-1)
    {
        merge(a, i, i + gap - 1, len - 1);
    }
}

/*
 *  Merge sort ( From bottom to top )
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     len --  Length of array 
 */
void merge_sort_down2up(int a[], int len)
{
    int n;

    if (a==NULL || len<=0)
        return ;

    for(n = 1; n < len; n*=2)
        merge_groups(a, len, n);
}

void main()
{
    int i;
    int a[] = {80,30,60,40,20,10,50,70};
    int ilen = LENGTH(a);

    printf("before sort:");
    for (i=0; i<ilen; i++)
        printf("%d ", a[i]);
    printf("\n");

    merge_sort_up2down(a, 0, ilen-1);        //  Merge sort ( From the top down )
    //merge_sort_down2up(a, ilen);            //  Merge sort ( From bottom to top )

    printf("after  sort:");
    for (i=0; i<ilen; i++)
        printf("%d ", a[i]);
    printf("\n");
}

Merge sort C++ Realization
Implementation code (MergeSort.cpp)

/**
 *  Merge sort ：C++
 *
 * @author skywang
 * @date 2014/03/12
 */

#include <iostream>
using namespace std;

/*
 *  Merge two adjacent ordered intervals in an array into one 
 *
 *  Parameter description ：
 *     a --  An array containing two ordered intervals 
 *     start --  The first 1 The starting address of an ordered interval .
 *     mid   --  The first 1 The end address of an ordered interval . Also the first 2 The starting address of an ordered interval .
 *     end   --  The first 2 The end address of an ordered interval .
 */
void merge(int* a, int start, int mid, int end)
{
    int *tmp = new int[end-start+1];    // tmp Is summary 2 A temporary area in an orderly area 
    int i = start;            //  The first 1 Index of an ordered area 
    int j = mid + 1;        //  The first 2 Index of an ordered area 
    int k = 0;                //  Index of staging area 

    while(i <= mid && j <= end)
    {
        if (a[i] <= a[j])
            tmp[k++] = a[i++];
        else
            tmp[k++] = a[j++];
    }

    while(i <= mid)
        tmp[k++] = a[i++];

    while(j <= end)
        tmp[k++] = a[j++];

    //  The sorted elements , All integrated into the array a in .
    for (i = 0; i < k; i++)
        a[start + i] = tmp[i];

    delete[] tmp;
}

/*
 *  Merge sort ( From the top down )
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     start --  The starting address of the array 
 *     endi --  The end address of the array 
 */
void mergeSortUp2Down(int* a, int start, int end)
{
    if(a==NULL || start >= end)
        return ;

    int mid = (end + start)/2;
    mergeSortUp2Down(a, start, mid); //  Recursive sorting a[start...mid]
    mergeSortUp2Down(a, mid+1, end); //  Recursive sorting a[mid+1...end]

    // a[start...mid]  and  a[mid...end] It's two ordered spaces ,
    //  Sort them into an ordered space a[start...end]
    merge(a, start, mid, end);
}


/*
 *  An array a Do several mergers ： Array a The total length of is len, Divide it into several parts with a length of gap Subarray ;
 *              take " Every time 2 Adjacent subarrays "  Merge sort .
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     len --  Length of array 
 *     gap --  Length of subarray 
 */
void mergeGroups(int* a, int len, int gap)
{
    int i;
    int twolen = 2 * gap;    //  The length of two adjacent subarrays 

    //  take " Every time 2 Adjacent subarrays "  Merge sort .
    for(i = 0; i+2*gap-1 < len; i+=(2*gap))
    {
        merge(a, i, i+gap-1, i+2*gap-1);
    }

    //  if  i+gap-1 < len-1, Then one of the remaining sub arrays is not paired .
    //  Merge the subarray into the sorted array .
    if ( i+gap-1 < len-1)
    {
        merge(a, i, i + gap - 1, len - 1);
    }
}

/*
 *  Merge sort ( From bottom to top )
 *
 *  Parameter description ：
 *     a --  Array to sort 
 *     len --  Length of array 
 */
void mergeSortDown2Up(int* a, int len)
{
    int n;

    if (a==NULL || len<=0)
        return ;

    for(n = 1; n < len; n*=2)
        mergeGroups(a, len, n);
}

int main()
{
    int i;
    int a[] = {80,30,60,40,20,10,50,70};
    int ilen = (sizeof(a)) / (sizeof(a[0]));

    cout << "before sort:";
    for (i=0; i<ilen; i++)
        cout << a[i] << " ";
    cout << endl;

    mergeSortUp2Down(a, 0, ilen-1);        //  Merge sort ( From the top down )
    //mergeSortDown2Up(a, ilen);            //  Merge sort ( From bottom to top )

    cout << "after  sort:";
    for (i=0; i<ilen; i++)
        cout << a[i] << " ";
    cout << endl;

    return 0;
}

Merge sort Java Realization
Implementation code (MergeSort.java)

/**
 *  Merge sort ：Java
 *
 * @author skywang
 * @date 2014/03/12
 */

public class MergeSort {

    /*
     *  Merge two adjacent ordered intervals in an array into one 
     *
     *  Parameter description ：
     *     a --  An array containing two ordered intervals 
     *     start --  The first 1 The starting address of an ordered interval .
     *     mid   --  The first 1 The end address of an ordered interval . Also the first 2 The starting address of an ordered interval .
     *     end   --  The first 2 The end address of an ordered interval .
     */
    public static void merge(int[] a, int start, int mid, int end) {
        int[] tmp = new int[end-start+1];    // tmp Is summary 2 A temporary area in an orderly area 
        int i = start;            //  The first 1 Index of an ordered area 
        int j = mid + 1;        //  The first 2 Index of an ordered area 
        int k = 0;                //  Index of staging area 

        while(i <= mid && j <= end) {
            if (a[i] <= a[j])
                tmp[k++] = a[i++];
            else
                tmp[k++] = a[j++];
        }

        while(i <= mid)
            tmp[k++] = a[i++];

        while(j <= end)
            tmp[k++] = a[j++];

        //  The sorted elements , All integrated into the array a in .
        for (i = 0; i < k; i++)
            a[start + i] = tmp[i];

        tmp=null;
    }

    /*
     *  Merge sort ( From the top down )
     *
     *  Parameter description ：
     *     a --  Array to sort 
     *     start --  The starting address of the array 
     *     endi --  The end address of the array 
     */
    public static void mergeSortUp2Down(int[] a, int start, int end) {
        if(a==null || start >= end)
            return ;

        int mid = (end + start)/2;
        mergeSortUp2Down(a, start, mid); //  Recursive sorting a[start...mid]
        mergeSortUp2Down(a, mid+1, end); //  Recursive sorting a[mid+1...end]

        // a[start...mid]  and  a[mid...end] It's two ordered spaces ,
        //  Sort them into an ordered space a[start...end]
        merge(a, start, mid, end);
    }


    /*
     *  An array a Do several mergers ： Array a The total length of is len, Divide it into several parts with a length of gap Subarray ;
     *              take " Every time 2 Adjacent subarrays "  Merge sort .
     *
     *  Parameter description ：
     *     a --  Array to sort 
     *     len --  Length of array 
     *     gap --  Length of subarray 
     */
    public static void mergeGroups(int[] a, int len, int gap) {
        int i;
        int twolen = 2 * gap;    //  The length of two adjacent subarrays 

        //  take " Every time 2 Adjacent subarrays "  Merge sort .
        for(i = 0; i+2*gap-1 < len; i+=(2*gap))
            merge(a, i, i+gap-1, i+2*gap-1);

        //  if  i+gap-1 < len-1, Then one of the remaining sub arrays is not paired .
        //  Merge the subarray into the sorted array .
        if ( i+gap-1 < len-1)
            merge(a, i, i + gap - 1, len - 1);
    }

    /*
     *  Merge sort ( From bottom to top )
     *
     *  Parameter description ：
     *     a --  Array to sort 
     */
    public static void mergeSortDown2Up(int[] a) {
        if (a==null)
            return ;

        for(int n = 1; n < a.length; n*=2)
            mergeGroups(a, a.length, n);
    }

    public static void main(String[] args) {
        int i;
        int a[] = {80,30,60,40,20,10,50,70};

        System.out.printf("before sort:");
        for (i=0; i<a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.printf("\n");

        mergeSortUp2Down(a, 0, a.length-1);        //  Merge sort ( From the top down )
        //mergeSortDown2Up(a);                    //  Merge sort ( From bottom to top )

        System.out.printf("after  sort:");
        for (i=0; i<a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.printf("\n");
    }
}

above 3 The principle and output of the two implementations are the same . Here is their output ：

before sort:80 30 60 40 20 10 50 70 
after  sort:10 20 30 40 50 60 70 80