On merging and sorting

Interview questions ： What are the ideas of quick arrangement and merging based on

answer ： Based on the idea of divide and rule

Ideological concept

Merge sort , english MERGE-SORT, utilize Merger Thought , Use the classic Divide and conquer （divide-and-conquer） Strategy to achieve sorting . The essence of this is division and treatment , Many people may be familiar with fast platoon , Bubble and other familiar sorting methods , Not very good at merging and sorting .

You can see that this algorithm is very similar to a complete binary tree , By dividing the data into small piles , Then sort and combine these data , It's a divide and rule strategy . You can also understand it as splitting the item first , Then merge the same items , The final result is what we want .

#include <iostream> void Merge(int r[], int r1[], int s, int m, int t){
       int i = s;    int j = m + 1;    int k = s;    while (i <= m && j <= t)    {
           if (r[i] <= r[j])            r1[k++] = r[i++];        else            r1[k++] = r[j++];    }    if (i <= m)        while (i <= m)            r1[k++] = r[i++];    else        while (j <= t)            r1[k++] = r[j++];    for (int n = s; n <= t; n++)        r[n] = r1[n];} void MergeSort(int r[], int r1[], int s, int t){
       if (s < t)    {
           int m = (s + t) / 2;        MergeSort(r, r1, s, m);        MergeSort(r, r1, m + 1, t);        Merge(r, r1, s, m, t);    }} int main(){
       int r[8] = {10, 3, 5, 1, 9, 34, 54, 565}, r1[8];    MergeSort(r, r1, 0, 7);    for (int q = 0; q < 8; q++)        std::cout << r[q] << std::ends;    return 0;}

Algorithm complexity

And the sorting time complexity is O(N*logN), Additional space complexity O(N).

Merge sort comparison takes up memory , But it is an efficient and stable algorithm .

application

Based on quick sort , Make a few adjustments to complete the merging and sorting .

Small and problem

See this problem , An implementation method we can easily think of is ： double for Loop traversal , Find a number smaller than the current number , Add up . The time complexity of this method is O(n^2).

def merge_sort(arr):    #  Recursively decompose the array , When there is only one element left , Stop decomposing     if len(arr) == 1:        return arr, 0    mid = len(arr) // 2    left, sum_left = merge_sort(arr[:mid])    right, sum_right = merge_sort(arr[mid:])    #  Merging arrays     arr, sum = merge(sum_left + sum_right, left, right)    return arr, sum

def merge(sum, left, right):    i = j = 0    arr = []    while (i < len(left) and j < len(right)):        if left[i] < right[j]:            arr.append(left[i])            sum += left[i] * (len(right) - j)            i += 1        else:            arr.append(right[j])            j += 1    while (i < len(left)):        arr.append(left[i])        i += 1
    while (j < len(right)):        arr.append(right[j])        j += 1    return arr, sum

if __name__ == '__main__':    arr = [2, 3, 8, 6, 7, 4, 5]    print(merge_sort(arr)[1])

Reverse order pair problem

We need to arrange the array in descending order , Every time I merge , Find a number larger on the left than on the right ,print. Empathy , Because arrays are merged in descending order every time , therefore , When a number on the left is greater than a number on the right , So it is greater than all the numbers after the number on the right .

def merge_sort(arr):    #  Recursively decompose the array , When there is only one element left , Stop decomposing     if len(arr) == 1:        return arr    mid = len(arr) // 2    left = merge_sort(arr[:mid])    right = merge_sort(arr[mid:])    #  Merging arrays     arr = merge(left, right)    return arr

def merge(left, right):    i = j = 0    arr = []    while (i < len(left) and j < len(right)):        if left[i] > right[j]:            arr.append(left[i])            print('(' + str(left[i]) + ',' + str(right[j]) + ')')            tmp_j = j+1            while (tmp_j < len(right)):                print('(' + str(left[i]) + ',' + str(right[tmp_j]) + ')')                tmp_j += 1            i += 1        else:            arr.append(right[j])            j += 1    while (i < len(left)):        arr.append(left[i])        i += 1
    while (j < len(right)):        arr.append(right[j])        j += 1    return arr

if __name__ == '__main__':    arr = [2, 3, 8, 6, 7, 4, 5]    print(merge_sort(arr))

Optimize

Detect natural ordered sub segments in the sequence , If a strictly descending sub segment is detected, the sequence is reversed to an ascending sub segment , In the best case, whether ascending or descending, the time complexity will be o(n), It has strong adaptability . This method becomes Timsort.

summary

Many people may be acm Some programming competitions will study this algorithm , In the actual work project, if not to study the underlying source code , You won't be exposed to this merging sort . In the actual interview, as long as you can say the general idea of divide and rule , I think the interviewer will let you pass .