Ok, ho capito. In realtà non ti serve memorizzare entrambi i valori booleani estratti dai due controlli: è sufficiente che non appena un controllo fallisce ritorni false.
In genere è una questione di performance (ti eviti di eseguire elaborazioni non necessarie, alleggerendo la computazione)... ma ad esempio, ricordo che in università avevo un professore che voleva il return solo alla fine dei metodi. Insomma, informati come preferiscono da te.

Allora:
- devi sostituire TUTTE le occorrenze della variabile "a" che sono ancora maiuscole: Java è case-sensitive e, se compilato, il metodo ti segnalerebbe errore;
- attenzione che non chiudi MAI le parentesi graffe dei cicli for
- come operatori logici di congiunzione (AND) e disgiunzione (OR) è meglio usare "&&" oppure "||"
- boolean left = true deve essere dichiarato fuori dal for, come fai con "right": se no, non appena esci dal ciclo è come se non esistesse più (e non compilerebbe, visto che poi cerchi di utilizzarlo a fondo programma)
- è ridondante utilizzare un if-else se poi uno dei due rami non contiene codice... è sufficiente invertire la logica e usare solo if. Nel primo caso puoi fare
codice:
if (!(j % 2 == 0 && a[j] < a[i]))
... prova tu a sistemare anche gli altri due
- si vede che sei allergico alle doppie : l'operatore di confronto è "==", non "=" (if della seconda condizione)

Per rispondere alla tua ultima domanda: si parte da 1 perchè, se iniziassi da 0, alla prima iterazione l'elemento i - 1 sarebbe -1... e dunque non valido

Comunque: sia chiaro che con i miei appunti non voglio farti da professore...!