Ταξινόμηση με εισαγωγή

Γραφική Αναπαράσταση Ταξινόμησης με Εισαγωγή

Η ταξινόμηση με εισαγωγή είναι ένας απλός αλγόριθμος ταξινόμησης που δημιουργεί τον τελικό ταξινομημένο πίνακα (ή λίστα) αλλάζοντας ένα στοιχείο κάθε φορά. Είναι λιγότερο αποτελεσματική σε μεγάλες λίστες σε αντίθεση με άλλους αλγορίθμους όπως είναι η γρήγορη ταξινόμηση (quicksort), η ταξινόμηση με σωρό (heapsort), ή η ταξινόμηση με συγχώνευση (merge sort). Ωστόσο, η ταξινόμηση με εισαγωγή παρέχει πολλά πλεονεκτήματα:

Είναι απλή στην εφαρμογή της.
Αποτελεσματική για (πολύ) μικρά σύνολα δεδομένων.
Αποδοτική για σύνολα δεδομένων που είναι ήδη ταξινομημένα με χρονική πολυπλοκότητα O(n + d), όπου d είναι ο αριθμός των αναστροφών.
Πιο αποτελεσματική στην πράξη από άλλους απλούς τετραγωνικούς (όπως, O(n²)) αλγορίθμους όπως είναι η ταξινόμηση με επιλογή (selection sort) ή η ταξινόμηση φυσαλίδας (bubble sort), όπου στην καλύτερη περίπτωση (σχεδόν ταξινομημένα τα στοιχεία κατά την είσοδο) ο χρόνος εκτέλεσης είναι Ο(n).
Ευσταθής, δηλαδή, δεν αλλάζει τη σχετική σειρά των στοιχείων που έχουν ίσα κλειδιά.
Σε χώρο, καθώς απαιτεί μόνο σταθερό μέγεθος, δηλαδή Ο(1), επιπλέον μνήμης.
Σε απευθείας σύνδεση, καθώς μπορεί να ταξινομήσει μια λίστα καθώς τη λαμβάνει.

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

Αλγόριθμος

Ένα παράδειγμα ταξινόμησης με εισαγωγή που γίνεται επιτόπου είναι το παραπάνω. Επιλέγει το 2ο στοιχείο από τον πίνακα και ελέγχει κάθε στοιχείο με βάση αυτό. Αν είναι μεγαλύτερο (από ό,τι είναι το στοιχείο στην προηγούμενη θέση που ελέγχτηκε), το αφήνουμε ως έχει (όπως συμβαίνει με το 8). Εάν, τώρα, είναι μικρότερο από ό,τι το προηγούμενο, μετατοπίζουμε τα μεγαλύτερα στοιχεία μέχρι να συναντήσει το μικρότερο στοιχείο, όπου και κάνει εκεί την εισαγωγή.

Η ταξινόμηση με εισαγωγή εκτελεί συνεχόμενες επαναλήψεις αλλάζοντας ένα στοιχείο εισόδου σε κάθε επανάληψη και δημιουργώντας με αυτόν τον τρόπο μία ταξινομημένη λίστα εξόδου. Σε κάθε επανάληψη, η ταξινόμηση με εισαγωγή μετακινεί ένα στοιχείο από τη λίστα εισόδου, αφού έχει βρει την τοποθεσία που ανήκει η ταξινομημένη λίστα και το εισάγει εκεί. Τη διαδικασία αυτή την επαναλαμβάνει μέχρι να μην υπάρχουν άλλα στοιχεία εισόδου.

Η επιλογή των στοιχείων γίνεται την ίδια στιγμή, με επανάληψη σε όλο τον πίνακα, και τοποθετώντας το επιλεγμένο στοιχείο στην ταξινομημένη λίστα με αποτέλεσμα να μεγαλώνει η λίστα κατά μία θέση. Σε κάθε θέση του πίνακα ελέγχει την τιμή σύμφωνα με τη μεγαλύτερη τιμή στην ταξινομημένη λίστα (η οποία τυχαίνει να είναι μετά από αυτή στον προηγούμενο έλεγχο θέσης του πίνακα). Εάν είναι μεγαλύτερη, τότε αφήνει το στοιχείο στη θέση του και μετακινείται προς την επόμενη θέση. Εάν είναι μικρότερη τότε βρίσκει τη σωστή θέση με βάση την ταξινομημένη λίστα και μεταθέτει όλες τις μεγαλύτερες τιμές μέχρι να δημιουργηθεί ένα κενό και εισάγει σε αυτό τη σωστή τιμή.

Ο τελικός πίνακας μετά από k επαναλήψεις έχει την ιδιότητα ότι και η k+1 καταχώρηση θα είναι ταξινομημένη («+1» επειδή η πρώτη καταχώρηση παραλείπεται). Σε κάθε επανάληψη η πρώτη υπόλοιπη καταχώρηση από την είσοδου αφαιρείται και εισάγεται στη σωστή θέση το αποτέλεσμα, επεκτείνοντας έτσι το αποτέλεσμα:

Πίνακας εισόδου

Γίνεται:

Με κάθε στοιχείο μεγαλύτερο του x να αντιγράφεται στα δεξιά μετά από σύγκριση με αυτό.

Η πιο συνηθισμένη παραλλαγή της ταξινόμησης με εισαγωγή, η οποία λειτουργεί με πίνακες, μπορεί να περιγραφεί όπως παρακάτω:

Ας υποθέσουμε ότι υπάρχει μια συνάρτηση που ονομάζεται Εισαγωγή και έχει σχεδιαστεί για να εισαγάγετε μια τιμή σε μια ταξινομημένη ακολουθία στην αρχή ενός πίνακα. Λειτουργεί αρχίζοντας από το τέλος της ακολουθίας και μετατοπίζοντας κάθε στοιχείο μία θέση προς τα δεξιά μέχρι να βρεθεί μία κατάλληλη θέση για το νέο στοιχείο. Η συνάρτηση αντικαθιστά την τιμή που είναι αποθηκευμένη αμέσως μετά την ταξινομημένη ακολουθία στον πίνακα.
Για να πραγματοποιηθεί μία ταξινόμηση με εισαγωγή, ξεκινάμε από το πιο αριστερό στοιχείο του πίνακα και επικαλούμαστε Εισαγωγή για να εισάγουμε κάθε τυχαίο στοιχείο στη σωστή θέση. Η εντολή αλληλουχίας, μέσω της οποίας το στοιχείο που εισάγεται, αποθηκεύεται στην αρχή του πίνακα στην ομάδα των στοιχείων που έχουν ήδη εξεταστεί. Σε κάθε ταξινόμηση αντικαθιστά μία μόνο τιμή μεταβλητής: η τιμή που εισάγεται.

Ακολουθεί ο ψευδοκώδικας ενός ολοκληρωμένου αλγορίθμου, όπου οι πίνακες είναι αρχικοποιημένοι με μηδέν:

 //οι τιμές στον πίνακα Α[i] ελέγχονται με τη σειρά, ξεκινώντας από το δεύτερο στοιχείο
 for i ← 1 to i ← length(A)-1
   {
   // κατά την έναρξη της επανάληψης, τα στοιχεία Α[0 ... i-1] είναι σε ταξινομημένη σειρά
   // αυτή η επανάληψη θα εισάγει ένα Α[i] στην ταξινομημένη σειρά

     //θα αποθηκεύσει στο A[i] την τιμή που θα εισαχθεί στον πίνακα σε αυτή την επανάληψη
     valueToInsert ← A[i]
     
     //θα ορίσει τη θέση i ως θέση-τρύπα, όπου Α[i]=A[holePos] που θα είναι τώρα άδεια
     holePos ← i
     // στη συνέχεια θα μετακινήσει τη θέση-τρύπα προς τα κάτω μέχρι το valueToInsert 
     //να είναι μεγαλύτερο 
    //βρίσκει τι είναι ακριβώς κάτω από την θέση-τρύπα ή αν η θέση-τρυπα έχει γίνει το 1ο 
    //στοιχείο του πίνακα

     while holePos > 0 and valueToInsert < A[holePos - 1]
       { //εαν η τιμή της εισαγωγής δεν ταιριάζει στη θέση-τρύπα τότε γίνεται μετατόπιση
         
         A[holePos] ← A[holePos - 1] //μετατόπιση της μεγαλύτερης τιμής προς τα πάνω
         holePos ← holePos - 1       //μετακίνηση της θέσης-τρύπας προς τα κάτω
       }

      //η θέση-τρύπα είναι στη σωστή θέση, οπότε τοποθετούμε την τιμή valueToInsert μέσα στη 
      //θέση-τρύπα
     A[holePos] ← valueToInsert
     //ο πίνακας A[0..i] είναι τώρα ταξινομημένος
   }

Σημειώστε ότι, αν και συνηθίζεται η εφαρμογή του αλγορίθμου και η επιλογή των στοιχείων να γίνεται την ίδια στιγμή, πράγμα που απαιτεί να γίνεται ο έλεγχος των στοιχείων σε σειρά, η σειρά του ελέγχου (και της αντικατάστασης) των στοιχείων που εισάγονται είναι πραγματικά τυχαία. Η επιλογή μπορεί να γίνει χρησιμοποιώντας σχεδόν οποιοδήποτε μοτίβο, εφ' όσον όλα τα στοιχεία εισόδου έχουν τελικά ελεγχθεί (και αντικατασταθεί από την είσοδο).

Καλύτερη, χειρότερη και μέση περίπτωση

Κινούμενη εικόνα για την ταξινόμηση με εισαγωγή 30 στοιχείων ενός πίνακα.

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

Η απλούστερη χειρότερη περίπτωση εισόδου είναι ένας πίνακας ταξινομημένος με την αντίστροφη σειρά. Το σύνολο όλων περιπτώσεων χειρότερης εισόδου περιλαμβάνει όλους τους πίνακες των οποίων κάθε στοιχείο είναι το μικρότερο ή το δεύτερο μικρότερο από τα στοιχεία που βρίσκονται πριν από αυτό. Σε αυτές τις περιπτώσεις κάθε επανάληψη στον εσωτερικό βρόχο θα σαρώσει και θα μετακινήσει το σύνολο του ταξινομημένου υποτμήματος του πίνακα πριν εισάγει το επόμενο στοιχείο. Αυτό έχει σαν αποτέλεσμα η ταξινόμηση με εισαγωγή εκτελείται σε τετραγωνικό χρόνο (δηλαδή Ο(n²)).

Η μέση περίπτωση είναι, επίσης, η τετραγωνική, η οποία χρησιμοποιεί ταξινόμηση με εισαγωγή που είναι πρακτική για ταξινόμηση σε μεγάλους πίνακες. Ωστόσο, η ταξινόμηση με εισαγωγή είναι ένας από τους γρηγορότερους αλγορίθμους για ταξινόμηση πολύ μικρών πινάκων, ακόμα πιο γρήγορα και από ότι η γρήγορη ταξινόμηση (quicksort). Πράγματι, οι καλές εφαρμογές γρήγορης ταξινόμησης χρησιμοποιούν ταξινόμηση με εισαγωγή για πίνακες μικρότερους από ένα συγκεκριμένο όριο, ακόμα και όταν προκύπτει ως υποπρόβλημα. Το ακριβές όριο πρέπει να είναι προσδιορισμένο πειραματικά και να εξαρτάται από το μηχάμημα, αλλά είναι συνήθως γύρω στο δέκα.

Παράδειγμα: Ο πίνακας που ακολουθεί δέιχνει τα βήματα για την ταξινόμηση της ακολουθίας { 3, 7, 4, 9, 5, 2, 6, 1 }. Σε κάθε βήμα, το στοιχείο που εξετάζεται είναι υπογραμμισμένο. Το στοιχείο που μετακινείται (ή παραμένει στη θέση του επειδή θεωρείται ακόμα μεγαλύτερος) στο προηγούμενο βήμα εμφανίζεται με έντονο χρώμα.

3 7 4 9 5 2 6 1

3 4 7 9 5 2 6 1

3 4 5 7 9 2 6 1

2 3 4 5 7 9 6 1

2 3 4 5 6 7 9 1

1 2 3 4 5 6 7 9

Σύγκριση με άλλους αλγορίθμους ταξινόμησης

Η ταξινόμηση με εισαγωγή είναι παρόμοια με την ταξινόμηση επιλογής(selection sort). Όπως στην ταξινόμηση επιλογής, αφού το k περάσει σε έναν πίνακα, τα πρώτα k στοιχεία του πίνακα είναι ταξινομημένα. Για την ταξινόμηση επιλογής, αυτά είναι τα k μικρότερα στοιχεία, ενώ για την ταξινόμηση με εισαγωγή είναι ότι και τα k πρώτα στοιχεία στον μη ταξινομημένο πίνακα. Το πλεονέκτημα της ταξινόμησης με εισαγωγή είναι ότι σαρώνει μόνο όσα στοιχεία είναι απαραίτητα για να καθορίσουν τη σωστή τοποθεσία των k συν το πρώτο στοιχείο, ενώ η ταξινόμηση επιλογής πρέπει να σαρώσει όλα τα εναπομείναντα στοιχεία για να βρει το ακριβές μικρότερο στοιχείο.

Οι υπολογισμοί δείχνουν ότι η ταξινόμηση με εισαγωγή συνήθως εκτελεί περίπου τις μισές συγκρίσεις σε σχέση με την ταξινόμηση επιλογής. Υποθέτοντας ότι η θέση του k συν το πρώτο στοιχείο είναι τυχαία, η ταξινόμηση με εισαγωγή θα απαιτήσει κατά μέσο όρο ολίσθηση των μισών από τα προηγούμενα k στοιχεία, ενώ η ταξινόμηση επιλογής απαιτεί πάντα σάρωση όλων των μη ταξινομημένων στοιχείων. Εάν ο πίνακας εισόδου είναι ταξινομημένος αντίστροφα, η ταξινόμηση με εισαγωγή εκτελεί τόσες συγκρίσεις όσες και η ταξινόμηση επιλογής. Εάν ο πίνακας εισαγωγής είναι ήδη ταξινομημένος, η ταξινόμηση επιλογής εκτελεί τόσες λίγες συγκρίσεις όσες n-1, καθιστώντας έτσι την ταξινόμηση με εισαγωγή πιο αποτελεσματική όταν τις δίνονται ταξινομημένοι ή «σχεδόν ταξινομημένοι» πίνακες.

Ενώ η ταξινόμηση με εισαγωγή τυπικά εκτελεί λιγότερες συγκρίσεις σε σχέση με την ταξινόμηση επιλογής, απαιτεί περισσότερες εγγραφές διότι ο εσωτερικός βρόχος μπορεί να χρειαστεί ολίσθηση μεγάλων τμημάτων του ταξινομημένου μέρους του πίνακα. Γενικά, η ταξινόμηση με εισαγωγή γράφει στον πίνακα σε χρόνο O(n²), ενώ αντίθετα η ταξινόμηση επιλογής γράφει σε χρόνο μόνο O(n). Για το λόγο αυτό και η ταξινόμηση επιλογής προτιμάται σε περιπτώσεις όπου η εγγραφή στη μνήμη είναι σημαντικά πιο δαπανηρή απ’ ότι η ανάγνωση όπως με το EEPROM ή τη flash μνήμη(flash memory).

Μερικοί αλγόριθμοι Διαίρει και βασίλευε (υπολογιστές) όπως η γρήγορη ταξινόμηση(quicksort) and ταξινόμηση με συγχώνευση ταξινομούν διαιρώντας αναδρομικά τη λίστα σε μικρότερες υπό-λίστες, οι οποίες μετά ταξινομούνται. Μια χρήσιμη βελτίωση στην πράξη για αυτούς τους αλγορίθμους είναι η χρήση ταξινόμησης με εισαγωγή για την ταξινόμηση μικρών υπό-λιστών, όπου η ταξινόμηση με εισαγωγή υπερτερεί όλων αυτών των πιο περίπλοκων αλγορίθμων. Το μέγεθος της λίστας για το οποίο η ταξινόμηση με εισαγωγή πλεονεκτεί ποικίλλει ανάλογα με το περιβάλλον και την υλοποίηση, αλλά τυπικά είναι για οκτώ μέχρι είκοσι στοιχεία.

Παραλλαγές

Ο D.L. Shell έκανε σημαντικές βελτιώσεις στον αλγόριθμο• η τροποποιημένη εκδοχή ονομάζεται ταξινόμηση με κέλυφος(shell sort). Ο αλγόριθμος ταξινόμησης συγκρίνει στοιχεία που διαχωρίζονται από μια απόσταση που μειώνεται σε κάθε πέρασμα. Η ταξινόμηση με κέλυφος έχει βελτιώσει σημαντικά τους χρόνους εκτέλεσης σε πρακτική εργασία, με δύο απλές παραλλαγές που απαιτούν O(n^3/2) and O(n^4/3) χρόνους εκτέλεσης.

Εάν το κόστος των συγκρίσεων υπερβαίνει το κόστος των ανταλλαγών, όπως στην περίπτωση για παράδειγμα των κλειδιών με αναφορά ή με ανθρώπινη αλληλεπίδραση( όπως για παράδειγμα διαλέγοντας ένα από τα ζευγάρια που εμφανίζονται το ένα δίπλα στο άλλο), μετά χρησιμοποιώντας δυαδική ταξινόμηση με εισαγωγή μπορούμε να επιτύχουμε καλύτερη εκτέλεση. Η δυαδική ταξινόμηση χρησιμοποιεί μια δυαδική αναζήτηση για να καθορίσει τη σωστή τοποθεσία για την εισαγωγή νέων στοιχείων, οπότε εκτελεί ⌈log₂(n)⌉ συγκρίσεις στη χειρότερη περίπτωση, που είναι O(n log n). Ο αλγόριθμος στο σύνολό του ακόμη έχει ένα χρόνο εκτέλεσης O(n²) κατά μέσο όρο λόγω του αριθμού των ανταλλαγών που απαιτούνται για κάθε εισαγωγή.

Ο αριθμός των ανταλλαγών μπορεί να μειωθεί υπολογίζοντας τη θέση πολλαπλών στοιχείων πριν τη μετακίνησή τους. Για παράδειγμα, εάν η θέση προορισμού δύο στοιχείων έχει υπολογιστεί πριν μετακινηθούν στη σωστή θέση, ο αριθμός των ανταλλαγών μπορεί να μειωθεί περίπου 25% για τυχαία δεδομένα. Στην ακραία περίπτωση αυτή η παραλλαγή λειτουργεί περίπου όμοια με την ταξινόμηση με συγχώνευση.

Για να αποφύγουμε να κάνουμε μια σειρά από ανταλλαγές για κάθε εισαγωγή, η είσοδος μπορεί να αποθηκευθεί σε μια συνδεδεμένη λίστα(linked list), η οποία επιτρέπει στα στοιχεία να συνδεθούν μέσα ή έξω από τη λίστα σε διαρκή χρόνο όταν η θέση στη λίστα δεν είναι γνωστή. Βέβαια, αναζητώντας την συνδεδεμένη λίστα απαιτεί να ακολουθεί διαδοχικά τους συνδέσμους τη επιθυμητής θέσης: μια συνδεδεμένη λίστα δεν έχει τυχαία πρόσβαση, οπότε δε μπορεί να χρησιμοποιήσει μια πιο γρήγορη μέθοδο όπως η δυαδική αναζήτηση. Για το λόγο αυτό, ο χρόνος εκτέλεσης που απαιτείται για αναζήτηση είναι Ο(n) και ο χρόνος για ταξινόμηση είναι O(n²). Αν χρησιμοποιείται μια πιο εξελιγμένη δομή δεδομένων (π.χ., στοίβα ή δυαδικό δέντρο), ο χρόνος που απαιτείται για αναζήτηση και ταξινόμηση μπορεί να μειωθεί σημαντικά. Αυτή είναι η ουσία της ταξινόμησης σωρού (heap sort) ή του δυαδικού δέντρου (binary tree sort).

Το 2004 οι Bender, Farach-Colton και Mosteiro δημοσίευσαν μια νέα παραλλαγή της ταξινόμησης με εισαγωγή με το όνομα ταξινόμηση βιβλιοθήκης(library sort) ή εισαγωγή με κενά που αφήνει ένα μικρό αριθμό από μη χρησιμοποιημένους χώρους (με άλλα λόγια, "κενά") τα οποίοι βρίσκονται διάσπαρτα σε όλο το εύρος του πίνακα. Τα πλεονεκτήματα είναι ότι οι ταξινομήσεις χρειάζονται ολίσθηση στοιχείων μέχρι να βρεθεί σε κενό. Οι συγγραφείς δείχνουν ότι αυτός ο αλγόριθμος ταξινόμησης τρέχει με υψηλή πιθανότητα σε O(n log n) χρόνο.^[2]

Αν χρησιμοποιείται μια skip list ο χρόνος μειώνεται σε O(log n), και οι ανταλλαγές δε χρειάζονται επειδή η skip list είναι υλοποιημένη σε δομή συνδεδεμένη λίστα. Ο τελικός χρόνος εκτέλεσης της ταξινόμησης θα ήταν O(n log n).

Η ταξινόμηση με εισαγωγή σε λίστα είναι μια παραλλαγή της ταξινόμησης με εισαγωγή. Μειώνει τον αριθμό των κινήσεων. ^{[εκκρεμεί παραπομπή]}

Κώδικας της ταξινόμησης με εισαγωγή σε λίστα σε C

Εάν τα στοιχεία είναι αποθηκευμένα σε συνδεδεμένη λίστα τότε η λίστα μπορεί να ταξινομηθεί σε O(1) επιπλέον χώρο. Ο αλγόριθμος ξεκινά με μια αρχικά κενή (και ως εκ τούτου τυχαία ταξινομημένη) λίστα. Τα στοιχεία εισόδου αφαιρούνται από τη λίστα ένα τη φορά και στη συνέχεια εισάγονται στο σωστό σημείο στην ταξινομημένη λίστα. Όταν η λίστα εισόδου είναι κενή, τότε οι ταξινομημένες λίστες έχουν το επιθυμητό αποτέλεσμα.

Ο αλγόριθμος χρησιμοποιεί trailing δείκτη^[3] για την εισαγωγή στην ταξινομημένη λίστα. Μια πιο απλή αναδρομική μέθοδος αναδομεί τη λίστα κάθε φορά (αντί να τη διασπά) και μπορεί να χρησιμοποιήσει O(n) χώρο στοίβας.

struct LIST
{
  struct LIST * pNext;
  int           iValue;
};

struct LIST * SortList(struct LIST * pList)
{
  /* δημιουργία του ταξινομημένου πίνακα από κενή λίστα */
  struct LIST * pSorted = NULL;

  /* εξαγωγή ένα ένα των στοιχείων της λίστας εισαγωγής μέχρι να μείνει κενή */
  while (pList != NULL)
    {
      /* θυμίζουμε το πρώτο στοιχείο λίστας */
      struct LIST *   pHead  = pList;
      /* μετακινούμε το δείκτη για αποτελεσματική σύνδεση */
      struct LIST ** ppTrail = &pSorted;

      /* εξαγωγή του πρώτου στοιχείου της λίστας */
      pList = pList->pNext;

      /* εισαγωγή του πρώτου στοιχείου της λίστας στην ταξινομημένη λίστα στη σωστή θέση */
      while (TRUE)
        {
          /* ανήκει το πρώτο στοιχείο εδώ; */
          if (*ppTrail == NULL || pHead->iValue < (*ppTrail)->iValue)
            {
              /* εάν ανήκει */
              pHead->pNext = *ppTrail;
              *ppTrail = pHead;
              break;
            }
          else
            {
              /* εάν δεν ανήκει - συνέχιση στο υπόλοιπο της λίστας */
              ppTrail = & (*ppTrail)->pNext;
            }
        }
    }

  return pSorted;
}

Παραπομπές

↑ Robert Sedgewick, Algorithms, Addison-Wesley 1983 (chapter 8 p. 95)
↑ Bender, Michael A.; Farach-Colton, Martín; Mosteiro, Miguel (2004), Insertion Sort is O(n log n), PSU, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.9.3665
↑ Hill, Curt, επιμ.., «Trailing Pointer Technique», Euler, Valley City State University, http://euler.vcsu.edu:7000/11421/, ανακτήθηκε στις 2012-09-22 .

Bender, Michael A; Farach-Colton, Martín; Mosteiro, Miguel (2006), Insertion Sort is O(n log n), SUNYSB, http://www.cs.sunysb.edu/~bender/newpub/BenderFaMo06-librarysort.pdf ; also http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.60.3758; republished? in Theory of Computing Systems (ACM) 39 (3), Ιούνιος 2006, http://dl.acm.org/citation.cfm?id=1132705 .
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), «2.1: Insertion sort», Εισαγωγή στους αλγορίθμους (2η έκδοση), MIT Press and McGraw-Hill, σελ. 15–21, ISBN 0-262-03293-7 .
Knuth, Donald (1998), «5.2.1: Sorting by Insertion», The Art of Computer Programming, 3. Sorting and Searching (2η έκδοση), Addison-Wesley, σελ. 80–105, ISBN 0-201-89685-0 .
Sedgewick, Robert (1983), «8», Algorithms, Addison-Wesley, σελ. 95ff, ISBN 978-0-201-06672-2, https://archive.org/details/algorithms00sedg/page/95 .