Analysis of Merging Sorting of Ten Sorting Algorithms in Java

Principle of catalog merging and sorting merging and sorting API design merging and sorting code to realize time complexity analysis of merging and sorting

Merging and sorting principle

1. Split one set of data into two subgroups with equal elements as much as possible, and continue to split each subgroup until the number of elements in each subgroup after splitting is 1.
2. Combine two adjacent subgroups into an ordered large group.
3. Repeat Step 2 until there is only one group.

Merge and sort API design

类名	Merge
构造方法	Merge():创建Merge对象
成员方法	1.public static void sort(Comparable[] a):对数组内的元素进行排序 2.private static void sort(Comparable[] a,int lo,int hi):对数组a中从索引lo到索引hi之间的元素进行排序 3.private static void merge(Comparable[] a,int lo,int mid,int hi):从索引lo到索引mid为1个子组，从索引mid+1到索引hi为另1个子组，把数组a中的这两个子组的数据合并成1个有序的大组(从索引lo到索引hi) 4.private static boolean less(Comparable v,Comparable w):判断v是否小于w 5.private static void exchange(Comparable[] a,int i,int j):交换a数组中，索引i和索引j处的值
成员变量	private static ComParable[] assit:完成归并操作需要的辅助数组

Implementation of merging and sorting code

public class Merge {
    // Auxiliary array 
    private static Comparable[] assist;
    // Pair array a Sorts the elements in the 
    public static void sort(Comparable[] a){
        assist=new Comparable[a.length];
        int lo=0;
        int hi=a.length-1;
        sort(a,lo,hi);
    }
    // Pair array a From lo To hi Sorts the elements of 
    private static void sort(Comparable[] a,int lo,int hi){
        if(hi<=lo){
            return;
        }
        int mid=lo+(hi-lo)/2;
        // Right lo To mid Sort the elements between 
        sort(a,lo,mid);
        // Right mid+1 To hi Sort the elements between 
        sort(a,mid+1,hi);
        // Right lo To mid This set of data and mid To hi This set of data is merged 
        merge(a,lo,mid,hi);
    }
    // In the array, from the lo To mid For 1 Group, from mid+1 To hi For 1 Group, merging the two sets of data 
    public static void merge(Comparable[] a,int lo,int mid,int hi){
        //lo To mid This set of data and mid+1 To hi This set of data is merged into a secondary array assist At the corresponding index 
        int i=lo;// Definition 1 Pointers to assist The index that begins to populate the data in the array 
        int p1=lo;// Definition 1 A pointer to the 1 The first of the group data 1 Elements 
        int p2=mid+1;// Definition 1 A pointer to the 2 The first of the group data 1 Elements 
        // Compare the size of the elements in the left group and the right group, and fill the data in the assist Array 
        while(p1<=mid&&p2<=hi){
            if(less(a[p1],a[p2])){
                assist[i++]=a[p1++];
            }else{
                assist[i++]=a[p2++];
            }
        }
        // Fill the unfilled data into the assist Medium 
        while(p1<=mid){
            assist[i++]=a[p1++];
        }
        while(p2<=hi){
            assist[i++]=a[p2++];
        }
        for(int index=lo;index<=hi;index++){
            a[index]=assist[index];
        }
    }
    // Comparison v Element is less than w Element 
    private static boolean less(Comparable v,Comparable w){
        return v.compareTo(w)<0;
    }
    // Array element i And j Switch position 
    private static void exchange(Comparable[] a,int i,int j){
        Comparable t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
 
}
// Test code 
 class Test{
    public static void main(String[] args) {
        Integer[] a={8,4,6,5,7,1,3,6,2};
        Merge.sort(a);
        System.out.println(Arrays.toString(a));
    }
}

Time Complexity Analysis of Merge Sorting

Merge sorting is the most typical example of divide-and-conquer thought. In the above algorithm, a [lo... hi] is sorted, which is divided into a [lo... mid] and a [mid+1. hi], sorted separately by recursive calls, and finally the ordered subarrays are merged into the final sorting result. The outlet of this recursion is that if an array can no longer be divided into two sub-arrays, merge will be performed for merging, and the size of elements will be judged for sorting during merging.

A tree diagram is used to describe merging. If an array has 8 elements, it will divide by 2 each time to find the smallest subarray, and split log 8 times, with a value of 3, so the tree has 3 layers. Then the top-down k layer has 2 k subarrays, each array has a length of 2 (3-k), and merging needs 2 (3-k) comparisons at most. Therefore, the number of comparisons per layer is 2 ^ k * 2 ^ (3-k) = 2 ^ 3, so the total number of three layers is 3 * 2 ^ 3.

Assuming that the number of elements is n, the number of times of merging and sorting is log2 (n). Therefore, there are log2 (n) layers, then log2 (n) is used to replace 3 of the above 3 * 2 3, and the final time complexity of merging and sorting is: log2 (n) * 2 (log2 (n)) = log2 (n) * n. According to the derivation rule of large O, ignoring the base, the final time complexity of merging and sorting is O (nlogn);
Disadvantages of merge sorting:
It is necessary to apply for extra array space, which leads to the increase of space complexity, which is a typical operation of exchanging space for time.