1

Below merge sort is a good implementation? I did not want to create temp arrays for merging. I just wanted to merge inline.

Can you provide any additional feedback to consider?

   // sort(arr,0, arr.length - 1);


    void sort(int[] arr, int left, int right){
        if(right - left < 1)
            return;
        int mid = (left + (right - left) / 2);
        sort(arr, left, mid);
        sort(arr,mid + 1, right);
        merge(arr, left, mid, right);
    }

    void merge(int[] arr, int left, int mid, int right){
        int j = mid + 1;
        for (int i = left; i <= mid; i++) {
            j = mid + 1;
            if(arr[i] > arr[j]){ // compare left array with right array first element
                swap(arr, i, j);
                while(j < right && arr[j] > arr[j + 1]){
                    swap(arr, j, j + 1);
                    j++;
                }
            }
        }
    }

    void swap(int[] arr, int i, int j){
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
RamPrakash
  • 2,218
  • 3
  • 25
  • 54
  • 1
    Your merge is O(N^2), so this is O(N^2 * log N) all together -- super slow. – Matt Timmermans Apr 30 '21 at 01:38
  • @MattTimmermans, do you have any suggestions to make this faster? that is the point of original question anyway. – RamPrakash Apr 30 '21 at 01:59
  • 1
    The merge sort seems to be impossible inline, you need temp arrays: https://softwareengineering.stackexchange.com/questions/297160/why-is-mergesort-olog-n#:~:text=The%20complexity%20of%20merge%20sort,and%20NOT%20O(logn).&text=The%20divide%20step%20computes%20the,for%20even%20n)%20elements%20each. – Michael Rovinsky Apr 30 '21 at 06:47

0 Answers0