מיון הכנסה

מיון הכנסה (באנגלית: Insertion sort) הוא אלגוריתם מיון השוואתי פשוט. האלגוריתם מחלק את הרשימה לשני חלקים – תת-רשימה ממוינת בחלק השמאלי, ותת-רשימה לא ממוינת בחלק הימני. בכל שלב, האלגוריתם לוקח את האיבר הראשון מהתת-רשימה הלא ממוינת ומכניס אותו למקומו הנכון בתת-הרשימה הממוינת, תוך הזזת האיברים הגדולים ממנו ימינה כדי לפנות מקום. תהליך זה ממשיך עד שכל האיברים עברו לחלק הממוין. 

זמן הריצה הממוצע של האלגוריתם הוא  פעולות (בדומה למיון בועות).  במקרה הטוב ביותר, כאשר הרשימה כבר ממוינת, זמן הריצה שלו משתפר ל-. הוא נחשב לפתרון יעיל עבור רשימות שהן כמעט ממוינות . היות שהאלגוריתם דורש מעט מאוד פעולות הכנסה והזזות, מה שמקנה לו יתרון משמעותי. 

 תיאור האלגוריתם 
בכל איטרציה (מעבר על המערך) נלקח איבר ממערך הקלט, ומוכנס למקומו הנכון בתוך ה"תת-מערך" הממוין שנבנה, במהלך המיון, בחלק השמאלי של המערך. לאחר השלב הראשון כולל האזור הממוין במערך את שני האיברים הראשונים, לאחר מכן את שלושת האיברים הראשונים וכן הלאה. כך עד לסיומו של מערך הקלט. המיון נעשה במקום, כלומר ללא צורך בזיכרון נוסף, פרט למערך עצמו ולתא עזר בודד.

דוגמה לקוד דמה עבור מערך המתחיל באינדקס 0:
 for j ←1 to length(A)-1
     key ← A[ j ]
     > A[ j ] is added in the sorted sequence A[0, .. j-1]
     i ← j - 1
     while i >= 0 and A [ i ] > key
         A[ i + 1 ] ← A[ i ]
         i ← i - 1
     A [i + 1] ← key
דוגמה למימוש עבור מערך מכל סוג נתונים שהוא (בשפת C):
void insert_sort (void *arr, size_t num, size_t size, int (*cmp) (const void *, const void *))
{
    void *key;
    size_t j;
    int i;

    key = malloc (size);

    for (j = 1 ; j < num ; j++)
    {
        memcpy (key, (void *) ((char *) arr + size * j), size);

        i = j - 1;
        while (i >= 0 && cmp ((char *) arr + size * i, key))
        {
            memcpy ((char *) arr + size * (i + 1), (char *) arr + size * i, size);
            memcpy ((char *) arr + size * i, key, size);

            i--;
        }
    }

    free (key);
}

 חישוב סיבוכיות 
אם נגדיר כשלב ראשון את ההסתכלות על מקומות 1 ו־2 (או למען הקיצור עד מקום 2 במערך), אז שלב שני יהיה הסתכלות עד מקום 3, שלב שלישי הסתכלות עד מקום 4, וכן הלאה, ולכן, בסך הכל יהיו n-1 שלבים כדי למיין מערך שמכיל n מקומות.
לכן, במקרה הכי גרוע, בשלב הראשון תבוצע פעולת החלפה אחת (שמורכבת ממספר סופי של פעולות) (כלומר, החלפה בין המקום הראשון והמקום השני), בשלב השני יבוצעו 2 פעולות החלפה (שמורכבות ממספר סופי של פעולות) (כלומר החלפה בין המקום השלישי למקום השני ואז בין המקום השני למקום הראשון), בשלב השלישי 3 פעולות החלפה וכן הלאה, עד שבשלב ה־n-1)לפי ההגדרה הוא השלב האחרון במיון (יבוצעו n-1 פעולות החלפה, ולכן מספר הפעולות חסום למעשה על ידי  פעולות החלפה (כאשר כל פעולת החלפה מכילה עד מספר קבוע של פעולות) השווה ל- פעולות (לפי הגדרת סכום סדרה חשבונית).
ומכאן שסיבוכיות זמן הריצה (במקרה הגרוע) שייכת ל-.
סיבוכיות הזיכרון היא  בגלל שמשתמשים במספר קבוע של משתנים נוספים כדי לבצע את המיון.

 קישורים חיצוניים 

 מיון הכנסה ב־Queue

הכנסה