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