我知道快速排序算法，但是我只关心合并排序算法。

我在互联网上发现了两种类型的合并排序算法实现。但是，当我将它们与插入算法进行比较时，它们的效率似乎较低，并且对于大量物品而言，这并不是预期的。

Enter the number of elements you want to sort:
300000

Time spent to executing BubbleSort: 362123 milliseconds
Time spent to executing Selection:  108285 milliseconds
Time spent to executing Insertion:   18046 milliseconds
Time spent to executing MergeSort:   35968 milliseconds
Time spent to executing MergeSort2:  35823 milliseconds

还有另一种方法来实现合并排序算法，使其比插入算法更有效吗？

看一下我的代码…

package br.com.test.test1;

import java.util.Random;
import java.util.Scanner;

 /**
 *
 * @author Joao
 */
public class Main {

    // generate an int array with random numbers between 0 and 500
    public static int[] generateRand(int n){
        int[] randArray = new int[n];
        Random number = new Random();

        // random numbers between 0 and 500
        for (int i = 0; i < n; i++){
            randArray[i] = number.nextInt(501);
        }
        return randArray;
    }

    public static void main(String[] args) {
        long startTime;
        Scanner input = new Scanner(System.in);
        int n;

        System.out.println("Enter the number of elements you want to sort:");
        n = input.nextInt();

        MyArray array = new MyArray(n);
        int[] aux = new int[n];
        aux = generateRand(n);


        array.copy(aux);   
        startTime = System.currentTimeMillis();
        array.bubblesort();
        // Time spent to executing BUBBLESORT 
        System.out.println("\nTime spent to executing BubbleSort: "+(System.currentTimeMillis() - startTime)+" milliseconds");


        array.copy(aux);   
        startTime = System.currentTimeMillis();
        array.selection();
        // Time spent to executing SELECTION 
        System.out.println("Time spent to executing Selection: "+(System.currentTimeMillis() - startTime)+" milliseconds");


        array.copy(aux);   
        startTime = System.currentTimeMillis();
        array.insertion();
        // Time spent to executing INSERTION 
        System.out.println("Time spent to executing Insertion: "+(System.currentTimeMillis() - startTime)+" milliseconds");


        array.copy(aux);   
        startTime = System.currentTimeMillis();
        array.mergeSort(0, n-1);
        // Time spent to executing MERGESORT 
        System.out.println("Time spent to executing MergeSort: "+(System.currentTimeMillis() - startTime)+" milliseconds");


        array.copy(aux);   
        startTime = System.currentTimeMillis();
        array.mergeSort2(0, n-1);
        // Time spent to executing MERGESORT 2
        System.out.println("Time spent to executing MergeSort2: "+(System.currentTimeMillis() - startTime)+" milliseconds");

    }
}

-—和------

package br.com.test.test1;

/**
 *
 * @author Joao Paulo
 */
class MyArray {
    private int[] v;
    private int n;  // array index
    private int len;

    public MyArray(int length) {
        len = length;
        v = new int[len];
        n = 0;
    }

    public void copy(int[] k){
        n = 0;
        for (int i = 0; i < len; i++) {
            v[i] = k[i];
            n++;
        }
    }

    public void show(){
        for (int i = 0; i < n; i++) {
            System.out.print(" " + v[i]);
        }
        System.out.println("\n");
    }


    // *******  START OF ALGORITHMS TO SORT  *******

    // ----------   Start of BubbleSort and Selection   --------------
    public void bubblesort(){
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n-1; j++) {
                if (v[j] > v[j+1]) {
                    change(j, j+1);
                }
            }
        }
    }

    public void selection() {
        int min;
        for (int i = 0; i < n-1; i++) {
            min = i;
            for (int j = i+1; j < n; j++){
                if (v[j] < v[min]){
                    min = j;
                }
            }
            change(i, min);
        }
    }

    private void change(int one, int two) {
        int temp = v[one];
        v[one] = v[two];
        v[two] = temp;
    }
    // ----------   End of BubbleSort and Selection   ----------------


    // ----------   Start of Insertion   -----------------------------
    public void insertion() {
        int i, j;
        int temp;
        for (i=1; i < n; i++) {
            temp = v[i];   // marked variable
            j = i;
            while ((j > 0) && (v[j-1] > temp)) {
                v[j] = v[j-1];
                j = j - 1;
            }
            v[j] = temp;
        }
    }
    // ----------   End of Insertion   -------------------------------


    // ----------   Start of MergeSort   -----------------------------
    public void mergeSort (int start, int end){
        if(start == end) return;

        int middle = (start+end)/2;
        mergeSort(start,middle);
        mergeSort(middle+1,end);
        merge(start,middle,end);
    }

    public void merge(int start, int middle, int end) {
        int[] aux = new int[v.length];

        for (int x = start; x <= end; x++) {
            aux[x] = v[x];
        }

        int i = start;
        int j = middle+1;
        int k = start;

        //emptying out array 'v' inserting items neatly in array 'aux' 
        while (i <= middle && j <= end) {
            if (aux[i] < aux[j]){
                v[k++] = aux[i++];
            } else {
                v[k++] = aux[j++];
            }
        }

        //copying values from 'aux' to 'v'
        while (i <= middle){
            v[k++] = aux[i++];
        }

        while (j <= end){
            v[k++] = aux[j++];
        }
    }
    // ----------   End of MergeSort   -------------------------------


    // ----------   Start of MergeSort 2  ----------------------------
    public void mergeSort2 (int start, int end) {
        if(start >= end) return;

        int middle = (start+end)/2;
        mergeSort2(start,middle);
        mergeSort2(middle+1,end);
        merge2(start,middle,end);
    }

    public void merge2(int start, int middle, int end) {
        int[] helper = new int[v.length];

        // Copy both parts into the helper array
        for (int i = start; i <= end; i++) {
            helper[i] = v[i];
        }

        int i = start;
        int j = middle + 1;
        int k = start;

        // Copy the smallest values from either the left or the right side back to the original array
        while (i <= middle && j <= end) {
            if (helper[i] <= helper[j]) {
                v[k] = helper[i];
                i++;
            } else {
                v[k] = helper[j];
                j++;
            }
            k++;
        }

        // Copy the rest of the left side of the array into the target array
        while (i <= middle) {
            v[k] = helper[i];
            k++;
            i++;
        }
        // Since we are sorting in-place any leftover elements from the right side
        // are already at the right position.
    }
    // ----------   End of MergeSort 2  ------------------------------

}