Una relazione d’ordine R su un insieme U è una relazione binaria che gode delle proprietà:

  • Riflessiva, \forall a \in U, aRa
  • Transitiva, \forall a, b, c \in U \text{ se } aRb \text{ e } bRc \text{ allora segue che } aRc
  • Anti-simmetrica, \forall a, b \in U \text{ se } aRb \text{ e } bRa \text{ allora } a=b

Alcuni esempi di relazioni d’ordine sono le relazioni di minore e uguale, o maggiore e uguale nei numeri reali, oppure l’inclusione tra i sotto-insiemi di un insieme dato. Una relazione d’ordine R su U è totale se \forall a,b \in U \text{ vale } aRb \text{ oppure } bRa . In questi casi si dice che R definisce un ordine lineare su U .

Un problema di ordinamento per un insieme U , secondo una relazione d’ordine totale R (\le) , può essere definito nel modo seguente, dato un vettore A tale che:
A=(A_{1}, A_{2}, \dots, A_{n}) \text{ con } n > 1 e con A[i] \in U \forall i \in \{1, 2, \dots, n \}

La soluzione dell’ordinamento è un vettore B tale che:
B=(B[1], B[2], \dots, B[n]) ottenuto permutando A , \mid B[i] \le B[i+1] \forall i \in \{1, 2, \dots, n-1\}

Le procedure utilizzate per risolvere il precedente problema si classificano in due gruppi distinti:

  • Ordinamento interno;
  • Ordinamento esterno.

Gli algoritmi di ordinamento interno necessitano che il vettore di input sia interamente presente in RAM durante il processo. In caso contrario i dati possono essere distribuiti su memorie di massa diverse.