לכל אחד מאלגוריתמי (שיטות) המיון קיימים שמות שונים (לדוגמא "מיון בועות" נקרא גם "מיון החלפה"), מימושים שונים (למשל באמצעות איטרציה, רקורסיה, מחסנית, תור, רשימה מקושרת, עץ בינארי וכו'), וגרסאות שונות (לדוגמא ל"מיון בועות" ישנן גרסאות כגון "מיון שייקר", "מיון מסרק"). כדי לפשט את הדברים, השתדלנו להתמקד בשמות, במימושים ובגירסאות הבסיסיים.
נוהגים למדוד סיבוכיות (יעילות) של מיונים, כדי לאפשר השוואה ביניהם.
יעילות יכולה להתבטא בכמות הזיכרון הנדרשת ובמהירות. המיונים האיטרטיביים דורשים פחות זיכרון אך הרקורסיביים יותר מהירים. במיונים נוטים לייחס את היעילות למהירות, ולכן נעדיף את הרקורסיביים. עם זאת, במערכים קטנים, המכילים בערך 10 איברים ומטה, הרקורסיביים איטיים יותר, לכן לקבלת אופטימיזציה (יעילות מרבית), במערכים קטנים הם יעברו לבצע מיון הכנסה.
נוהגים למדוד את הסיבוכיות של מיונים ע"פ הכמות המינימלית של פעולות שהם נדרשים לבצע, בכדי למיין קלט של מספרים, בהנחה שהפעולות הם המרכיב העיקרי של המהירות.
המדד ע"פ כמות ההשוואות וההחלפות אינו מדוייק, מאחר שמלבד הפעולות הללו, המיונים מבצעים פעולות רבות נוספות. אך הפעולות הנוספות, כמו השיפורים בין גירסאות שונות של אותו מיון, נחשבים "זניחים". סיבוכיות באה למדוד סדר גודל (הערכה) של יעלות ולא מדידה מדויקת.
נוהגים לחלק את הסיבוכיות של כל מיון ל 3 מקרים. הטוב ביותר, הממוצע והגרוע ביותר. (במיון בועות למשל, המקרה הגרוע ביותר הוא, שלפני המיון המספרים ממוינים בסדר הפוך. במקרה זה המיון יאלץ לבצע הכי הרבה פעולות. המקרה הטוב ביותר הוא, שלפני המיון המספרים כבר ממוינים בסדר הנכון. במקרה זה המיון יעצר אחרי האיטרציה הראשונה). אם זאת, הנטיה כמובן לייחס את החשיבות הגדולה ביותר למקרה הממוצע, שבו המספרים מסודרים בסדר אקראי. (במיון בועות למשל, מספיק שמספר קטן יחסית לשאר המספרים, יופיע לקראת סופם, בכדי לגרום צורך פעולות רבות עד להשלמת המיון, גם אם שאר המספרים מסודרים יחסית. מקרה זה נפוץ ולכן המיון הזה נחשב לגרוע ביותר).
יהי n הוא מספר האיברים שיש למיין. על אף הגרסאות והמימושים השונים, מייחסים למיונים בועות, בחירה והכנסה, על אף פשטותם האיטרטיבית, סיבוכיות ממוצעת של (O(n², ולמיונים הרקורסיביים מיזוג ומהיר, על אף מורכבותם הרקורסיבית, סיבוכיות ממוצעת של (O(n log n.
גם אם נצליח לשפר את הסיבוכיות בחצי, היא תחשב לאותה סיבוכיות (O(n²) = O(n²½, כי כאמור, סיבוכיות היא סדר גודל של וקבוע שמכפיל סיבוכיות נחשב זניח. אם זאת, כמובן שישנה משמעות לכל שיפור, בעיקר במיונים הרקורסיביים.
מיון מהיר נקרא בשמו, משום שהוא נחשב למהיר ביותר הידוע כיום.
ביבליוגרפיה (רשימת מקורות בהם נעשה שימוש במדריך זה):
