gogoWebsite

In 1945, John von Neumann invented the subsumption sort, a typical application of the partitioning algorithm.

define

Merge sort is an effective sorting algorithm built on the operation of subsumption, the algorithm is a very typical application of the use of Divide and Conquer (Divide and Conquer). The already ordered subsequences are merged to obtain a completely ordered sequence; that is, each subsequence is ordered first, and then the subsequence segments are ordered.

Algorithmic thinking

The merge sort algorithm has two basic operations, aingredient, which is the process of dividing the original array into two subarrays. The other iswipe out (a pest), which combines two ordered arrays into one larger ordered array.

1. The linear table to be sorted is continuously cut into several sub-tables until each sub-table contains only one element, at which point the sub-table containing only one element can be considered ordered.
2. Merge the sub-tables two by two, with each merge creating a new and longer ordered table, and repeat this step until finally there is only one sub-table left, and this sub-table is the ordered linear table.

graphical algorithm

Suppose we have an initial array of {8, 4, 5, 7, 1, 3, 6, 2} and the whole process of subsumption sorting is shown below.

divide and conquer

You can see that this structure is very much like a fully binary tree, this paper's subsumption sort we use recursion to achieve (can also be used in an iterative manner to achieve).ingredientThe stage can be understood as being the process of recursively splitting the molecular sequence with a recursion depth of log2n.

Merging two ordered arrays

Let's go over it again.wipe out (a pest)stage, we need to merge two already ordered subsequences into one ordered sequence, such as the last merge in the above figure, to merge two already ordered subsequences, [4,5,7,8] and [1,2,3,6], into the final sequence [1,2,3,4,5,6,7,8], to see the steps of implementation.

Animation Showcase

Algorithm Performance

Speed is second only to quick sort.

time complexity

O(nlogn)。

(math.) space complexity

O(N)The subsumption sort requires an array of the same length as the original array as an aid to sorting.

stability

stabilise。

code implementation

C and C++

void Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex){
    int i = startIndex, j=midIndex+1, k = startIndex;
    while(i!=midIndex+1 && j!=endIndex+1) {
        if(sourceArr[i] > sourceArr[j])
            tempArr[k++] = sourceArr[j++];
        else
            tempArr[k++] = sourceArr[i++];
    }
    while(i != midIndex+1)
        tempArr[k++] = sourceArr[i++];
    while(j != endIndex+1)
        tempArr[k++] = sourceArr[j++];
    for(i=startIndex; i<=endIndex; i++)
        sourceArr[i] = tempArr[i];
}
 
//Internal use of recursion
void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex) {
    int midIndex;
    if(startIndex < endIndex) {
        midIndex = startIndex + (endIndex-startIndex) / 2;//Avoid overflowint
        MergeSort(sourceArr, tempArr, startIndex, midIndex);
        MergeSort(sourceArr, tempArr, midIndex+1, endIndex);
        Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);
    }
}

int main(int argc, char * argv[]) {
    int a[8] = {50, 10, 20, 30, 70, 40, 80, 60};
    int i, b[8];
    MergeSort(a, b, 0, 7);
    for(i=0; i<8; i++)
        printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Java

package MergeSort;
public class MergeSort {
    public static int[] mergeSort(int[] nums, int l, int h) {
        if (l == h)
            return new int[] { nums[l] };
         
        int mid = l + (h - l) / 2;
        int[] leftArr = mergeSort(nums, l, mid); //left ordered array
        int[] rightArr = mergeSort(nums, mid + 1, h); //right ordered array
        int[] newNum = new int[ + ]; //New Ordered Arrays
         
        int m = 0, i = 0, j = 0;
        while (i < && j < ) {
            newNum[m++] = leftArr[i] < rightArr[j] ? leftArr[i++] : rightArr[j++];
        }
        while (i < )
            newNum[m++] = leftArr[i++];
        while (j < )
            newNum[m++] = rightArr[j++];
        return newNum;
    }
    public static void main(String[] args) {
        int[] nums = new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 10 };
        int[] newNums = mergeSort(nums, 0, - 1);
        for (int x : newNums) {
            (x);
        }
    }
}

Python

def MergeSort(lists):
    if len(lists) <= 1:
        return lists
    num = int( len(lists) / 2 )
    left = MergeSort(lists[:num])
    right = MergeSort(lists[num:])
    return Merge(left, right)

def Merge(left,right):
    r, l=0, 0
    result=[]
    while l<len(left) and r<len(right):
        if left[l] <= right[r]:
            (left[l])
            l += 1
        else:
            (right[r])
            r += 1
    result += list(left[l:])
    result += list(right[r:])
    return result

print MergeSort([1, 2, 3, 4, 5, 6, 7, 90, 21, 23, 45])