Example tutorial of comparison sort and merge sort (recursion)

A very important idea applied to the algorithm in merge sort - the divide and conquer method: decompose the original problem into several smaller but similar sub-problems - "Introduction to Algorithms". There are 3 steps in each level of recursion:

1. Decompose the problem
2. Solve the problem
3. Combine the solution to the problem
Example of the array to be sorted: {6, 5 , 3, 1, 7, 2, 4}, decompose its original sequence.

Through continuous recursive decomposition, you can see that the original array sequence has been continuously decomposed into the smallest units. Next, you may wish to regard them as leaf nodes of a binary tree.

　　

Merge and sort them in pairs to form a binary tree (also called a 2-way merge algorithm). It can be seen that the root node of the binary tree is the final sequence. In this process we complete the remaining two steps: problem solving and problem merging.

The theory is very simple, but the practice is very "complex". The theory of merge sort is very clear from the binary tree above. The original array to be sorted is continuously decomposed and finally regarded as the leaf nodes of the binary tree, and then they are arranged in twos to form new nodes, and gradually merged into one node. At this time The nodes are the sorted array sequences.

　Java

 1 package com.algorithm.sort.merge; 2  3 import java.util.Arrays; 4  5 /** 6  * 归并排序（递归） 7  * Created by yulinfeng on 2017/6/23. 8  */ 9 public class Merge {10     public static void main(String[] args) {11         int[] nums = {6, 5, 3, 1, 7, 2, 4};12         nums = mergeSort(nums);13         System.out.println(Arrays.toString(nums));14     }15 16     /**17      * 归并排序18      * @param nums 待排序数组序列19      * @return 排好序的数组序列20      */21     private static int[] mergeSort(int[] nums) {22         segment(nums, 0, nums.length - 1);23         return nums;24     }25 26     /**27      * 递归切分待排28      * @param nums 待切分数组29      * @param left 待切分最后第一个元素的索引30      * @param right 待切分数组最后一个元素的索引31      */32     private static void segment(int[] nums, int left, int right) {33         if (left >= right)34             return;35         // 找出中间索引36         int center = (left + right) / 2;37         // 对左边数组进行递归38         segment(nums, left, center);39         // 对右边数组进行递归40         segment(nums, center + 1, right);41         // 合并42         merge(nums, left, center, right);43     }44 45     /**46      * 两两归并排好序的数组（2路归并）47      * @param nums 带排序数组对象48      * @param left 左边数组的第一个索引49      * @param center 左数组的最后一个索引，center + 1右数组的第一个索引50      * @param right 右数组的最后一个索引51      */52     private static void merge(int[] nums, int left, int center, int right) {53         int[] tmpArray = new int[nums.length];54         int rightIndex = center + 1;   // 右数组第一个元素索引55         int tmpIndex = left;    //临时数组索引56         int begin = left;   // 缓存左数组第一个元素的索引，用于将排好序的数组拷贝回原数组57         while (left <= center && rightIndex <= right) {58             if (nums[left] <= nums[rightIndex]) {59                 tmpArray[tmpIndex++] = nums[left++];60             } else {61                 tmpArray[tmpIndex++] = nums[rightIndex++];62             }63         }64         while (left <= center) {65             tmpArray[tmpIndex++] = nums[left++];66         }67         while (rightIndex <= right) {68             tmpArray[tmpIndex++] = nums[rightIndex++];69         }70         while (begin <= right) {71             nums[begin] = tmpArray[begin++];72         }73     }74 }

　

Python3

 1 #二路归并排序（递归） 2 def merge_sort(nums): 3     segment(nums, 0, len(nums) - 1) 4     return nums 5  6 #切分待排序数组 7 def segment(nums, left, right): 8     if left >= right: 9         return10     center = int((left + right) / 2)11     segment(nums, left, center)12     segment(nums, center + 1, right)13     merge(nums, left, center, right)14 15 #两两归并排好序的数组（二路归并）16 def merge(nums, left, center, right):17     tmpArray = [0] * len(nums)18     rightIndex = center + 1     #右数组的第一个元素索引19     tmpIndex = left20     begin = left21     while left <= center and rightIndex <= right:22         if nums[left] <= nums[rightIndex]:23             tmpArray[tmpIndex] = nums[left]24             tmpIndex += 125             left += 126         else:27             tmpArray[tmpIndex] = nums[rightIndex]28             tmpIndex += 129             rightIndex += 130     while left <= center:31         tmpArray[tmpIndex] = nums[left]32         tmpIndex += 133         left += 134     while rightIndex <= right:35         tmpArray[tmpIndex] = nums[rightIndex]36         tmpIndex += 137         rightIndex += 138     while begin <= right:39         nums[begin] = tmpArray[begin]40         begin += 141 42 nums = [6, 5, 3, 1, 7, 2, 4]43 nums = merge_sort(nums)44 print(nums)