בהינתן מערך A של מספרים שלמים נגדיר מושג של היפוך אם
i<j ושניהם במסגרת האינדיקסים של המערך וגם האיבר באינדקס הנמוך יותר גדול מהאינדקס הגבוה
אז מצב זה נקרא היפוך

יתכן שמערך מכיל כמה היפוכים, לדוגמא מערך

7,1,10,12,3
(משמאל לימין)

מכיל 4 היפוכים 7,1 7,3 10,3 12,3

ומערך
5,4,3,2,1 מכיל 10 היפוכים

להסביר איך בעזרת (100nlog(n
פעולות ניתן לחשב את כמות ההיפוכים של המערך הנתון עם n איברים
נא לשים לב כי כמות ההיפוכים יכולה להיות n(n-1)/2
כלומר אי אפשר להשוות את כל הזוגות של המספרים כי זה יקח יותר פעולות ממה שדרוש בשאלה

קח את הindex של אותו איבר כול ההיפוכים שלו יהיו הindex שלו פחות מספר הפעמים שהוא מופיע.

עכשיו אחרי שהמערך ממויין מספר ההיפוכים הם בדיוק כמו הנוסחא שלך:

n(n-1)/2 (תוסיף לזה את מה שספרת בזמן המיון, והופ קיבלת את התוצאה בn log n במקרה הכי טוב, במקרה הגרוע n^2 יש מצב שיש פתרון טוב יותר, לא עולה לי עכשיו).