[JAVA] merge sort: dove sbaglio?

[afsdfdlecosdfsfdcco]

Ho scritto questo codice che dovrebbe implementare l'algoritmo Merge Sort ma c'è qualcosa che non va:

Codice PHP:

private static <T extends Comparable<T>> void mergeSort(T[] array,
        int leftIndex, int rightIndex, T[] leftArray, T[] rightArray) {
    if (leftIndex >= rightIndex)
        return;

    int middleIndex = (leftIndex + rightIndex) / 2;

    mergeSort(array, leftIndex, middleIndex, leftArray, rightArray);
    mergeSort(array, middleIndex + 1, rightIndex, leftArray, rightArray);

        /* Da qui fai il merge */
    int left = 0;
    int right = 0;
    int leftLength = middleIndex - leftIndex + 1;
    int rightLength = rightIndex - middleIndex;

    System.arraycopy(array, leftIndex, leftArray, 0, leftLength);
    System.arraycopy(array, middleIndex + 1, rightArray, 0, rightLength);

    while ((left <= leftLength) && (right <= rightLength)) {
        array[leftIndex++] = (leftArray[left].compareTo(rightArray[right]) <= 0) // <--- QUI NullPointerException
                 ? leftArray[left++] : rightArray[right++]; 
    }

    while (leftIndex <= leftLength) {
        array[leftIndex++] = leftArray[leftIndex++];
    }

    while (rightIndex <= rightLength) {
        array[leftIndex++] = rightArray[rightIndex++];
    }
    }

///// edit:

    public static <T extends Comparable<T>> void mergeSort(T[] array) {
    int length = (array.length + 1) / 2;

    T[] leftArray = (T[]) new Comparable[length];
    T[] rightArray = (T[]) new Comparable[length];

    mergeSort(array, 0, array.length, leftArray, rightArray);
    } 


Cosa ho sbagliato?

Praticamente salta fuori una NullPointerException nel punto indicato nel sorgente (il problema è nel compareTo) e non riesco a sistemare... Forse è una stupidata ma con tutti quegli indici inizio a perdermi..

Grazie

edit:
ho poi un problema coi generici.. Ho bisogno di creare 2 vettori di tipo T ma a quanto pare non si puo'... :|
Ho "risolto" con
T[] leftArray = (T[]) new Comparable[length];
T[] rightArray = (T[]) new Comparable[length];
ma non mi pare una buona soluzione... Come si puo' fare in un modo un po' migliore?

[andbin]

Originariamente inviato da alecocco

Cosa ho sbagliato?

Diverse cose: innanzitutto non ci sarebbe alcun bisogno di creare degli array (nemmeno temporanei).

Come seconda cosa, limitare T in modo che debba essere per forza un Comparable, è troppo restrittivo. Arrays.sort() del collections framework infatti non fa così. C'è la versione che accetta Object[] e quella che accetta un T[] dove T può essere qualunque cosa, dedotta tramite inferenza. Non ci sono bounds. Per quella che prende un Object[], chiaramente nel metodo vengono fatti dei cast a Comparable ed è lì che bisogna essere certi che gli oggetti implementino davvero Comparable. Ma se io ti passo un Object[] me lo devi accettare, non rifiutare! Perché potrebbe contenere tutti String e sarebbe quindi corretto.

Terza cosa, anche volendo passare la tua scelta di usare come upper bound un Comparable, la tua signature sarebbe ancora troppo ristretta. Si deve sempre mettere:

.... Comparable<? super T>

E se ti domandi perché, ti rispondo che c'è un ottimo motivo. Io potrei fare una classe base Veicolo che implementa Comparable<Veicolo> e poi fare 2 sottoclassi Automobile e Moto che NON implementano Comparable (anche perché non sarebbe possibile, non si possono implementare più interfacce che hanno la stessa erasure).
Il risultato sarebbe che Automobile e Moto sono realmente Comparable, anche tra di loro (poi essendo Comparable su Veicolo, si presume che verranno comparati solo dati comuni in Veicolo, ovviamente).
Ma la tua signature non accetterebbe un Automobile[] o Moto[], perché accetterebbe Automobile[] solo se Automobile fosse Comparable<Automobile> mentre invece, nel mio esempio sopra, Automobile è Comparable<Veicolo>.

Troppo complicata la mia spiegazione?

[afsdfdlecosdfsfdcco]

Originariamente inviato da andbin

Diverse cose: innanzitutto non ci sarebbe alcun bisogno di creare degli array (nemmeno temporanei).

Ci devo lavorare sopra un pochetto

Originariamente inviato da andbin

....

Troppo complicata la mia spiegazione?

Ehm... si, mi sono perso quasi subito
Non ho molta esperienza coi generici

Intanto grazie ^^