Klingt für mich nach Mergesort. Bei Mergesort geht es darum, daß du das Array solange rekursiv in Unterarrays teilst, bis du einzelne Elemente hast. Dann baust du das Ganze wieder zusammen. Wenn du zwei Unterarrays zusammenbaust, dann prüfst du, ob das letzte Element des einen Unterarrays kleiner ist als das erste Element des anderen und klebst sie entsprechend zusammen.
Wenn ich seit dem Sommersemester nichts veressen habe sollte das schon der ganze Algorithmus sein.


Der Algorithmus sieht in etwa so aus (Achtung, rekursiv):
Code: 
array Mergesort(array A)
  WENN A nur ein Element beinhaltet
    Gebe A zurück
  SONST
    Teile A in zwei möglichst gleich große Unterarrays Au1 und Au2
    Mergesort(Au1)
    Mergesort(Au2)
    WENN (Au1[letzter] < Au2[erster])
      array Ergebnis = concat(Au1, Au2) // Hänge Au2 an Au1 an
    SONST
      array Ergebnis = concat(Au2, Au1) // Hänge Au1 an Au2 an
    Gebe Ergebnis zurück
Mit etwas Kenntnis deiner Sprache sollte es damit kein Problem sein, Mergesort zu implementieren.