Implementation of MergeSort recursion and non recursion

Focusing on the non recursive version, it actually simulates the process of doubling the length of a sub segment from 1 to the last full length. ]

The idea of merging is:
1. Sort the original array with two elements as a group, and then merge it into four groups and eight groups until the whole array is merged
2. When merging two subarrays, you need to use a temporary array to store the current merged two arrays
3. Copy the temporary array back to the corresponding position of the original array.

Finally, write the value of tmp array back to the original array. (note that merging is a stable sorting method!)

package mergesort;

import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;
//A non recursive algorithm for merging and sorting
public class MergeSort{
    public static void main(String args[]){
        MergeSort mer = new MergeSort();
        int[] array = mer.getArray();
        System.out.println("OriginalArray:" + Arrays.toString(array));
        mer.mergeSort(array);
        System.out.println("SortedArray:" + Arrays.toString(array));
    }
    public int[] getArray(){
        Scanner cin = new Scanner(System.in);
        System.out.print("Input the length of Array:");
        int length = cin.nextInt();
        int[] arr = new int[length];
        Random r = new Random();
        for(int i = 0; i < length; i++){
            arr[i] = r.nextInt(100);
        }
        cin.close();
        return arr;
    }
//////////Start/////////////////////////

    public void mergeSort(int[] a){
        int len = 1;         //Segment length starts at 1
        while(len < a.length){
            for(int i = 0; i < a.length; i += 2*len){  //Perform minor merge every 2*len segments
                merge(a, i, len);
            }
            len *= 2;
        }
    }

    public void merge(int[] a, int i, int len){
        int start = i;         //Start of left half
        int len_i = i + len;   //End marker bit of the first half, length of the left half len
        int j = i + len;       //Start of right half
        int len_j = j +len;    //End marker bit of the second half, length len of the right half
        int[] temp = new int[2*len];   //tmp array length 2*len
        int count = 0;
        while(i < len_i && j < len_j && j < a.length){  
            if(a[i] <= a[j]){
                temp[count++] = a[i++];
            }
            else{
                temp[count++] = a[j++];
            }
        }
        while(i < len_i && i < a.length){//Write the rest of each segment. Note: i may also exceed the array length here
            temp[count++] = a[i++];
        }
        while(j < len_j && j < a.length){
            temp[count++] = a[j++];
        }
        count = 0;         //Write the sorting result in tmp back to the original array
        while(start < j && start < a.length){
            a[start++] = temp[count++];
        }
    }
}

The implementation code of recursive algorithm is as follows:

public class MergeSort {
    public static void mergeSort(int[] data,int left,int right){ //Left and right are subscripts of digital elements
        if(left<right){
            int half=(left+right)/2;
            mergeSort(data,left,half);
            mergeSort(data,half+1,right);
            merge(data,left,right);
        }
    }
    public static void merge(int []a,int l,int h){
        int mid=(l+h)/2;
        int i=l;
        int j=mid+1;
        int count=0;
        int temp[]=new int[h-l+1];
        while(i<=mid&&j<=h){
            if(a[i]<a[j]){
                temp[count++]=a[i++];
            }else{
                temp[count++]=a[j++];
            }        
        }
        while(i<=mid){
            temp[count++]=a[i++];
        }
        while(j<=h){
            temp[count++]=a[j++];
        }
        count=0;
        while(l<=h){
            a[l++]=temp[count++];
        }
    }
   
}

The time complexity of merging and sorting is O(n*log2n), and the space complexity is O(n)

Merge sort is a stable sort method.

Tags: Java REST

Posted on Mon, 06 Jan 2020 19:20:27 -0800 by iPixel