DOMANDA Merge Sort ottimizzato con Insertion Sort

[SolidSnake4]

Buonasera a tutti,
ho un dubbio su l'ottimizzazione del merge sort tramite l'insertion sort, da richiamare ad un dato valore di soglia, che premetto di aver trovato tramite prove dei tempi tra mergesort ed insertion sort.
Il codice del merge sort modificato controllando il valore di soglia è il seguente, (tralascio il codice del merge):

public static void msort(int[] a, int n) {
 msort(a, 0, n-1);
}

public static void msort(int[] a, int fst, int lst) {
 if (lst - fst > 50) {
    int m = (lst + inf) / 2;
    msort(a, fst, m);
    msort(a, m+1, lst);
    merge(a, fst, m, lst);
 } else {
    isort(a, fst, lst);
 }
 
}

Mentre dell'insertion sort modificato in modo da essere richiamato su una porzione di array è il seguente:

public static void isort(int[] a, int fst, int lst) {
 if (lst < a.length) {
  for (int i = fst + 1; i <= lst; i++) {
   int j = i, x= a[i];

   while (j > fst && x < a[j-1]) {
    a[j] = a[j-1];
    j--;
   }

   a[j] = x;
  }
 }
}

Ora però ho un dubbio perchè alcune volte funziona altre no. Sapete dirmi dove sbaglio ?

 

[Itachi1991]

Scusa ma ho 2 domande (che credo siano abbastanza stupide):

- A che serve questa riga nel merge? int m = (lst + inf) >>> 1; (non dovrebbe fare la media?)
- La variabile inf la utilizzi in entrambe i metodi ma non la vedo instanziata, cosa è e dov'è instanziata?

 

[SolidSnake4]

- A che serve questa riga nel merge? int m = (lst + inf) >>> 1; (non dovrebbe fare la media?)

Infatti fa la media. L'operatore >>> 1, fa la divisione per due tra due interi evitando di causare overflow se i due valori lst inf superano il massimo valore di int. Niente di chè.

La variabile inf la utilizzi in entrambe i metodi ma non la vedo instanziata, cosa è e dov'è instanziata?

Ah scusa ho sbagliato a ricopiare è fst non inf.

Comunque ho già risolto, per ora, controllando se lst è uguale alla lunghezza dell'array. Se però qualcuno di voi trovasse qualcosa che ancora non va meglio ancora.

 

[SolidSnake4]

Ho risolto il problema, era la divisione con l'operatore >>> 1 che dava problemi, perchè alle volte prendeva un intero che superava la lunghezza dell'array.