שאלת מבחן במבני נתונים ומבוא לאלגוריתמים - האוניברסיטה הפתוחה 2018 - מיון

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

רמז: חשבו מה קורה כאשר כל האיברים נופלים לאותו דלי.

פתרון: **לא נכון.** מיון דלי (Bucket Sort) עובד בזמן לינארי **בממוצע** כאשר הקלט מפולג באופן אחיד. במקרה הגרוע, כל האיברים יכולים ליפול לאותו דלי, ואז המיון הפנימי של אותו דלי ייקח $O(n^2)$ (אם משתמשים במיון הכנסה) או $O(n \log n)$ (אם משתמשים במיון השוואתי יעיל). לכן הזמן במקרה הגרוע אינו לינארי.