Η μέθοδος αυτή εισάγει ένα-ένα τα στοιχεία του συνόλου που εξετάζεται στη σωστή τους θέση. Στη φάση i:

• υποθέτουμε ότι ο πίνακας Α[1..(i-1)] είναι ταξινομημένος,
• εισάγουμε το στοιχείο A[i] στην ακολουθία Α[1..(i-1)] στη σωστή θέση. Αυτό επιτυγχάνεται μετακινώντας όλα τα στοιχεία που είναι μεγαλύτερα του A[i] μία θέση δεξιά.

Κώδικας

Ο κώδικας που υλοποιεί τον αλγόριθμο δίνεται με μορφή διαδικασίας για τη ΓΛΩΣΣΑ και την C. Παράμετρος είναι ο πίνακας που θα ταξινομηθεί και το πλήθος των στοιχείων του.

Οι πίνακες στην C ξεκινούν από το στοιχεί 0 και φτάνουν στο n-1. Αυτό επιβάλει μερικές μικρές αλλαγές στον αλγόριθμο τόσο στο for όσο και στο while.

Ορθότητα

Τα στοιχεία του πίνακα Α[1..(i-1)] είναι ταξινομημένα. Το πρώτο στοιχείο της μη ταξινομημένης ακολουθίας Α[i..n], δηλαδή το Α[i] ελέγχεται με όλα τα στοιχεία του πίνακα Α[1..(i-1)] ξεκινώντας από το i-1 μέχρι να βρεθεί κάποιο μικρότερό του. Κάθε φορά που βρίσκεται ένα στοιχείο μεγαλύτερο του A[i] αυτό μετακινείται στην αμέσως μεγαλύτερη θέση.

Έστω ότι το A[k] (1<k<i-1) είναι μικρότερο του A[i]. Όταν βρεθεί ήδη όλα τα στοιχεία A[k+1..i-1] έχουν μετακινηθεί στην αμέσως μεγαλύτερη θέση τους, και το Α[i] τοποθετείται στη θέση A[k+1], οπότε τα στοιχεία Α[1..i] του πίνακα είναι ταξινομημένα.

Στην περίπτωση που δε βρεθεί στοιχείο μικρότερο του Α[i] τότε έχουμε φτάσει στην αρχή του πίνακα και το Α[i] τοποθετείται στη θέση A[1], ήδη όμως όλα τα στοιχεία Α[2..(i-1)] έχουν μετακινηθεί στην αμέσως μεγαλύτερη θέση τους, οπότε τα στοιχεία Α[1..i] του πίνακα είναι ταξινομημένα.

Μέσω του βρόχου while γίνεται η σύγκριση του Α[i] με τα στοιχεία Α[1..(i-1)]. Ο βρόχος τερματίζει πάντα όπως περιγράφηκε παραπάνω. Ο βρόχος for εξασφαλίζει ότι ελέγχονται όλα τα στοιχεία του πίνακα και τερματίζει όταν το i=n, οπότε όλα τα στοιχεία του πίνακα Α[1..n] είναι ταξινομημένα.

Χρονική Πολυπλοκότητα

Ο αλγόριθμος έχει δύο βρόχους εμφολιασμένους. Ο εσωτερικός βρόχος while, θεωρούμε ότι εκτελείται για κάθε i, άρα εκτελείται για i=2 μία φορά, για i=3 δύο φορές και για i=n, n-1 φορές, συνολικά n(n-1)/2 φορές.

Ο βρόχος for εκτελείται n φορές.

Ο συνολικός χρόνος για τον αλγόριθμο είναι:

Ο μεγαλύτερος όρος είναι ο n², άρα ο αλγόριθμος είναι τετραγωνικής πολυπλοκότητας Ο(n²).

Περίπτωση αρχικού ταξινομημένου πίνακα

Σε περίπτωση που ο πίνακας Α είναι ήδη ταξινομημένος η εντολή while δεν εκτελείται ποτέ γιατί πάντα key > A[j] (ή αλλιώς Α[i] > A[i-1] αφού key=A[i] και j=i-1) και η συνθήκη στο while είναι πάντα ψευδής. Σ' αυτή την περίπτωση η συνεισφορά της while είναι σταθερής πολυπλοκότητας. Τελικά έχουμε έναν εξωτερικό βρόχο ο οποίος εκτελείται n φορές και ο συνολικός χρόνος είναι T(n)=n. Οπότε, σ' αυτή την περίπτωση ο αλγόριθμος είναι γραμμικής πολυπλοκότητας O(n).

Χωρική Πολυπλοκότητα

Ο αλγόριθμος χρησιμοποιεί έναν πίνακα με n στοιχεία και τρεις μεταβλητές, την i, την j και την key. Αυτές οι μεταβλητές καταλαμβάνουν από μία θέση μνήμης η κάθε μία. Οπότε, συνολικά η θέσεις μνήμης που χρησιμοποιεί ο αλγόριθμος είναι:

S(n)=n+3

Η χωρική πολυπλοκότητα καθορίζεται από τον μεγαλύτερο όρο της εξίσωσης ο οποίος είναι ο n, δηλαδή, ο αλγόριθμος έχει γραμμική χωρική πολυπλοκότητα O(n).