Блог

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

     public static void mergeSort(int[] input, int start, int end) {
        if (end - start < 2)
            return;
        
        int mid = (start   end) / 2;
        mergeSort(input, start, mid);
        mergeSort(input, mid   1, end);
        merge(input, start, mid, end);
    }

    public static void merge(int[] input, int start, int mid, int end) {
        if (input[mid - 1] <= input[mid])
            return;
         
        int i = start;
        int j = mid;
        int tempIndex = 0;
        int[] temp = new int[end - start]; //combined size of both arrays being merged
        
        /*if i is >= mid, then that means the left portion of the array is done being sorted
          and vice versa if j >= end. Once this happens, we should be able to
          just copy the remaining elements into the temp array 
        */
        while (i < mid amp;amp; j < end) {
            temp[tempIndex  ] = (input[i] <= input[j]) ? input[i  ] : input[j  ];
        }
        
        //Copying left over elements in left portion
        while (i < mid)
            temp[tempIndex  ] = input[i  ];
        
        //Copying left over elements in right portion
        while (j < end)
            temp[tempIndex  ] = input[j  ];
        
        //Copy the sorted temp array into the original array
        //This is where I think I must be messing up
        for (int k = 0; k < temp.length; k  ) {
            input[start   k] = temp[k];    
        }
     }
  

Я думаю, что, должно быть, я неправильно копирую временный массив с отсортированными элементами обратно в исходный массив, но я не уверен. Я написал комментарии к своему коду, объясняющие мою логику.

Взгляните на следующие изменения:

1. Вычисление mid

   int mid = start (end — начало) / 2;

2. Правильное назначение указателей i, j.

   int i = начало; int j = середина 1;

3. Правильный размер временного массива.

   int [] temp = новый int[end-start 1];

4. Исправлено условие циклов while в коде.

     class Solution{
   
    public static void mergeSort(int[] input, int start, int end) 
    {
        if (end == start ) return;
   
        int mid = start   (end - start) / 2;
        mergeSort(input, start, mid);
        mergeSort(input, mid 1, end);
        merge(input, start, mid, end);
    }
   
     public static void merge(int[] input, int start, int mid, int end) {
        // No Need of the under mentioned instruction
        // if(input[mid-1] <= input[mid]) return;
   
        int i = start;
        int j = mid 1;
        int tempIndex = 0;
        int [] temp = new int[end-start 1]; //combined size of both arrays being merged
   
        /*if i is >= mid, then that means the left portion of the array is done being sorted and vice versa if j >= end. Once this happens, we should be able to just copy the remaining elements into the temp array */
   
        while(i <= mid amp;amp; j <= end){
            temp[tempIndex  ] = (input[i] <= input[j]) ? input[i  ] : input[j  ];
        }
   
        //Copying left over elements in left portion
        while(i <= mid)
            temp[tempIndex  ] = input[i  ];
   
        //Copying left over elements in right portion
        while(j <= end)
            temp[tempIndex  ] = input[j  ];
   
        //Copy the sorted temp array into the original array
        //This is where I think I must be messing up
        for(int k = 0; k < temp.length; k  ){
            input[start k] = temp[k];    
        }
     }
   
    public static void main(String[] args){
        int[] input = {9,4,6,8,5,7,0,2};
        mergeSort(input,0,7);
   
        for(int i : input)
            System.out.println(i);    
    }
   
    }