נתון מערך A בגודל n של מספרים חיוביים (לאו דווקא שלמים). ניתן להניח שהמספרים שונים זה מזה. ברצוננו לבנות מערך S בגודל n כך שבכל אינדקס i במערך S יהיה את כמות האיברים שנמצאים משמאל ל-i (כולל i) וקטנים או שווים מ-\(A[i]\) במערך המקורי.
לדוגמה, עבור \(A=[2,7,4,5,15,9,12]\), המערך שיתקבל הוא \(S=[1,2,2,3,5,5,6]\).

א. הראו שכל אלגוריתם לביצוע המשימה יבצע לפחות \(\Omega(n \log n)\) פעולות.
הראו תחילה שאם ניתן לבצע את המשימה שבשאלה בזמן \(T(n)\) כלשהו, אז ניתן לקבוע לכל איבר את מיקומו במערך הממוין בזמן \(O(T(n))\).

ב. תארו אלגוריתם לביצוע המשימה שרץ בזמן אופטימלי.

לסעיף א', בצעו רדוקציה ממיון. לסעיף ב', השתמשו במבנה נתונים המאפשר לבצע שאילתות על מספר האיברים הקטנים מערך מסוים ולהוסיף איבר חדש ביעילות.