אנו מעוניינים למיין אוסף של \(n\) מפתחות הלקוחים מתחום כלשהו \(U\).
נתונה טבלת גיבוב \(T\) בגודל \(m\) תאים, ופונקציית גיבוב כלשהי \(h\), הממפה באופן אחיד ופשוט מהתחום \(U\) אל השלמים בתחום \([0..m-1]\). פתרון התנגשויות נעשה באמצעות שרשור.

הניחו \(n \ge m\).

הוצע להשתמש באלגוריתם שלהלן:

1. הכנס את \(n\) המפתחות לטבלת הגיבוב \(T[0..m-1]\) באמצעות פונקציית הגיבוב \(h\).
2. מיין את המפתחות שברשימה המשורשרת של כל תא בטבלה באמצעות מיון מיזוג.
3. צרף את הרשימות הממוינות זו לזו לפי סדר התאים, החל מתא \(T[0]\) ועד \(T[m-1]\).

א. הראו באמצעות דוגמה נגדית, כי האלגוריתם לעיל אינו אלגוריתם מיון.

ב. מהו זמן הריצה של האלגוריתם במקרה הממוצע (כלומר תוחלת זמן הריצה), כפונקציה של \(n\) ו-\(m\)? יש להתחשב גם במקרה \(n = m\). הסבירו בקצרה.

ג. מהו זמן הריצה של האלגוריתם במקרה הגרוע? הסבירו בקצרה.

ד. נתון אוסף של \(n\) מספרים שלמים, המתפלגים באופן אחיד ובלתי תלוי זה בזה בתחום \(U = [0..n^2-1]\). הציגו פונקציית גיבוב \(h\) וגודל טבלה \(m\), שבאמצעותם האלגוריתם לעיל ימיין את אוסף המספרים בתוחלת זמן של \(O(n)\). נמקו את תשובתכם. האם יש סתירה בין סעיף זה לסעיף א'? נמקו.

ה. תארו אלגוריתם למיון אוסף המספרים המוגדר בסעיף ד' בזמן \(O(n)\) במקרה הגרוע. נמקו את זמן הריצה. האם אין כאן סתירה לחסם תחתון על מיונים? מדוע?