Per evitare vettori di dimensioni gigantesche ti consiglio il Marge sort, puoi vedere un esempio qui http://it.wikipedia.org/wiki/Merge_sort