Birleştirme türünün nasıl çalıştığını anlama

Question

private void merge(int[] array, int[] aux, int low, int mid, int hi) { 
    int i = low, j = mid + 1, k; 

    for (k = low; k <= hi; k++) { 
     aux[k] = array[k]; 
    } 
    for (k = low; k <= hi; k++) { 
     if (i > mid) { 
      array[k] = aux[j++]; 
     } else if (j > hi) { 
      array[k] = aux[i++]; 
     } else if (aux[j] < aux[i]) { 
      array[k] = aux[j++]; 
     } else /* if (aux[i] <= aux[j] */ { 
      array[k] = aux[i++]; 
     } 
    } 
} 

private void sort(int[] array, int[] aux, int lo, int hi) { 
    if (hi <= lo) { 
     return; 
    } 

    int mid = lo + (hi - lo)/2; 
    sort(array, aux, lo, mid); 
    sort(array, aux, mid + 1, hi); 
    merge(array, aux, lo, mid, hi); 
} 

public void mergeSort() {  
    int aux[] = new int[n]; 
    sort(ar, aux, 0, n - 1); 
} 

Kod çalışıyor ancak bunu anlayamıyorum.

1. Ben

   if (hi <= lo) { 
       return; 
   } 
   

   amacını anlıyorum ama dönüş yürütüldüğünde ne olur bilmiyorum.

2. Neden birleştirme işlevindeki son başka neden var anlamıyorum. Algoritma aux[3,5] olana kadar bölme yapıyorsa ve ben artan sıralamak istiyorum, else if, 5 < 3 karşılaştıracak ve bu, diğerine atlayacak ve 2 değeri değiştirmelidir.

Düzenleme: ayıklayıcı ile ve bu örnekte (3 33 1 55 66 34 67 45 23) ilk 2 değerleri ile birleştirme işlevini ulaştığı için biraz olmuştur. Sonuncu ise, 33 < 3'ü karşılaştırır ve sonuncuya girer. Eğer bu değerler doğru sırada ise, bu kod satırının noktası nedir? Diziden sonra [k] = aux [i ++]; dizinin değerini yürütülür [0] aux için [i ++] sorunu daha küçük alt problemlere ayrılmıştır sort yöntemde dizi [1]

Answer 1

1. olan tek olan aynıdır. Sıralama yapılacak aralık sadece bir veya sıfır geniş olduğunda, yapılacak hiçbir şey yoktur ve yöntem kapatılabilir. Bunun nedeni, tek bir öğenin tek başına tanım olarak sıralanmasıdır. Özyinlemenin like m0skit0 said durma durumudur.

2. Bu algoritmada öğeler değiştirilmemiştir. Metot iki sıralı diziyi birleştirir. Iki dizin i ve j vardır. i ortasına ulaştığında, sağ kısımdaki tüm elemanlar sonuç dizisine eklenir. j sağ kenarlığa ulaşırsa, sol bölümün tüm elemanları sonuca eklenir. Bu ilk iki durum.
   Şimdi, son iki durumda, algoritma, i ve j tarafından endekslenen geçerli öğelerin hangisinin minimum olduğunu bulmaya çalışır ve bunu sonuç dizisine ekler. Üçüncü durumda j'daki eleman küçüktür ve sonuç dizisine eklenir. Dördüncü durumda, i'daki eleman seçilir.