נתון מערך של מספרים טבעיים בעל התכונה הבאה: ההפרש בערך מוחלט בין כל שני איברים סמוכים במערך המקורי הוא לכל היותר 5.
א. מהי סיבוכיות הזמן של מיון המערך באמצעות אלגוריתם מיון הכנסה (Insertion Sort)? יש לספק חסם הדוק.
ב. הסבירו כיצד ניתן להתאים את אלגוריתם מיון מנייה (Counting Sort) לבעיה זו, ונתחו את סיבוכיותו. יש לספק חסם הדוק.
ג. בהינתן שני אלגוריתמי המיון, מיון הכנסה ומיון מנייה, האם ניתן לקבוע בוודאות איזה מהם יעיל יותר עבור בעיה זו? הסבירו במדויק ובתמציתיות.