Example display: Java implementation of merge sort algorithm and performance evaluation

Example demonstration: Using Java to implement the merge sort algorithm and perform performance testing

1. Introduction
Merge Sort (Merge Sort) is an efficient sorting algorithm , is widely used in actual development. It uses the idea of ​​​​Divide and Conquer to decompose the problem into multiple smaller sub-problems, and then merge the solutions of the sub-problems. This article will implement the merge sort algorithm through Java code and test its performance.

2. Principle of Merge Sort Algorithm
The core idea of ​​merge sort is to divide and conquer. The specific steps are as follows:

1. Divide the array to be sorted into two sub-arrays from the middle position.
2. Recursively sort these two sub-arrays respectively.
3. Merge the sorted sub-arrays to obtain the final ordered array.

3. Java code implementation
The following is a code example of using Java language to implement the merge sort algorithm:

public class MergeSort {
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
    }

    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid, temp);
            mergeSort(arr, mid + 1, right, temp);
            merge(arr, left, mid, right, temp);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        for (i = 0; i < k; i++) {
            arr[left + i] = temp[i];
        }
    }
}

4. Performance test
In order to conduct the merge sort algorithm For performance testing, we generate a set of random arrays for sorting and record the time required for sorting.

import java.util.Arrays;
import java.util.Random;

public class PerformanceTest {
    public static void main(String[] args) {
        int[] arr = generateRandomArray(1000000);
        System.out.println("排序前：" + Arrays.toString(arr));
        long startTime = System.currentTimeMillis();
        MergeSort.mergeSort(arr);
        long endTime = System.currentTimeMillis();
        System.out.println("排序后：" + Arrays.toString(arr));
        System.out.println("排序耗时：" + (endTime - startTime) + "毫秒");
    }

    private static int[] generateRandomArray(int length) {
        int[] arr = new int[length];
        Random random = new Random();
        for (int i = 0; i < length; i++) {
            arr[i] = random.nextInt(length);
        }
        return arr;
    }
}

In the above code, first use the generateRandomArray method to generate a set of random integer arrays with a length of 1000000, and then use the MergeSort.mergeSort method to sort the array, And record the time required for sorting. Finally, the sorted array and sorting time are output.

5. Summary
Through the above example demonstration, we implemented the merge sort algorithm through Java code and tested its performance. The merge sort algorithm is an efficient sorting algorithm that has good performance when faced with large-scale data sorting. Through the idea of ​​divide and conquer, merge sort can effectively decompose and solve the problem, thereby obtaining an orderly solution.

The above is the detailed content of Example display: Java implementation of merge sort algorithm and performance evaluation. For more information, please follow other related articles on the PHP Chinese website!