Понимание сортировки слиянием

Question

Ниже приведена Java-реализация сортировки слиянием, которую я сделал после посещения учебного пособия по алгоритму сортировки слиянием.

package com.test.sort;

import java.util.Scanner;


    ////100 80 90 70 60 40 50 30 10 20 //1 3 5 4 2
    public class MergeSortTest {

        private static int[] dataIntAry;

        public static void main(String[] args) {

            System.out.println("Enter data to be sorted : ");
            Scanner scanner = new Scanner(System.in);
            String data = scanner.nextLine();


            String[] dataAry = data.split("\\ ");

            dataIntAry = new int[dataAry.length];

            int cnt = 0;
            for (String dataEntity : dataAry) {
                dataIntAry[cnt] = Integer.parseInt(dataEntity);
                cnt++;
            }
            System.out.println("Array to operate on.");
            print(dataIntAry);
            System.out.println("===================================================================");

            sort(dataIntAry);


            System.out.println("###############################FINAL################################");

            print(dataIntAry);


        }



        private static void sort(int[] array) {

            performMergeSort(0, array.length-1);

        }

        private static void performMergeSort(int lowerIndex, int higherIndex) {
            System.out.println("Operating on array: ");
            print(dataIntAry, lowerIndex, higherIndex);

            //sort only if there is more than one elment in the array
            if(lowerIndex < higherIndex) {
                int middle = lowerIndex + ((higherIndex-lowerIndex)/2);


                performMergeSort(lowerIndex,middle);

                performMergeSort(middle+1, higherIndex);

                merge(lowerIndex,higherIndex);

            }


        }

        private static void merge(int lowerIndex, int higherIndex) {

            System.out.println("Merging array: ");
            print(dataIntAry, lowerIndex, higherIndex);

            for(int i=lowerIndex; i<=higherIndex; i++) {
                for(int j=i+1; j<=higherIndex; j++) {
                    if(dataIntAry[i] > dataIntAry[j]) {
                        int temp = dataIntAry[i];
                        dataIntAry[i] = dataIntAry[j];
                        dataIntAry[j] = temp;
                    }
                }
            }

            System.out.println("After Merge: ");
            print(dataIntAry, lowerIndex, higherIndex);

        }


        private static void print(int[] dataIntAry){
            System.out.println();
            for(int val: dataIntAry){
                System.out.print(val + " ");
            }
            System.out.println();
        }

        private static void print(int[] dataIntAry, int startIndex, int endIndex){
            Systegivingrintln();

            int index = 0;
            for(int val: dataIntAry){
                if(index >= startIndex && index <= endIndex)
                    System.out.print(val + " ");

                index++;
            }
            System.out.println();
        }

    }

Этот код сортирует массив, предоставленный во время выполнения. Прежде всего, я сомневаюсь, что реализация является базовой или нет! Если реализация верна, я действительно с подозрением отношусь к ее производительности. Как действительно убедиться, что реализация дает худшую производительность O (n log n)? Основной подозрительной частью здесь является метод merge () , где я делаю comapre и swap !.

Answer 1

Из вашего кода я думаю, что ваша часть слияния неверна. Вы должны объединить на основе нижнего, среднего и высшего индекса. Используйте приведенный ниже вызов метода

mergeParts(lowerIndex, middle, higherIndex);

вместо

merge(lowerIndex,higherIndex);

Пользователь ниже функции

private void mergeParts(int lowerIndex, int middle, int higherIndex) {

        for (int i = lowerIndex; i <= higherIndex; i++) {
            tempMergArr[i] = array[i];
        }
        int i = lowerIndex;
        int j = middle + 1;
        int k = lowerIndex;
        while (i <= middle && j <= higherIndex) {
            if (tempMergArr[i] <= tempMergArr[j]) {
                array[k] = tempMergArr[i];
                i++;
            } else {
                array[k] = tempMergArr[j];
                j++;
            }
            k++;
        }
        while (i <= middle) {
            array[k] = tempMergArr[i];
            k++;
            i++;
        }

    }

Сложность сортировки слиянием O (nlogn)

Поскольку сортировка слиянием делит массив на две половины на каждом этапе, что дает ему компонент log (n), а другой N-компонент получается из его сравнений, которые выполняются на каждом этапе. Таким образом, объединение становится почти O (nlog n).