רשימה מקושרת - מיון (MergeSort)

כדי למיין רשימות נשתמש ב-MergeSort: ניקח רשימה של N איברים ונתייחס אליה כאל N רשימות של איבר יחיד ולכן ממוינות. לאחר מכן בכל שלב נחלק את הרשימות לזוגות, ונאחד כל זוג רשימות ממוינות לרשימה ממוינת אחת. כך שבשלב הראשון ניקח את N הרשימות, ונהפוך אותן ל- [N/2] רשימות ממוינות, על-ידי כך שניקח כל זוג רשימות באורך אחד, נמיין את שני האיברים וניצור רשימה באורך שתיים. בשלב השני נהפוך [N/2] רשימות באורך 2 ל- [N/4] רשימות באורך 4, וכך עד לשלב האחרון בו נהפוך שתי רשימות ממוינות באורך של כ- [N/2] לרשימה ממוינת אחת באורך N.

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

יעילות

נחשב תחילה את היעילות של איחוד שתי רשימות ממוינות: לאחר כל השוואה, אנו מגלים את האיבר הבא ברשימה החדשה, היעילות של איחוד רשימות תהיה שווה לכן לכמות האיברים ברשימה החדשה. ולכן (O(M כאשר M הוא כמות האיברים ברשימה החדשה, ולכן ליניארית לכמות האיברים.

בסיום כל שלב בMergeSort, נקבל X רשימות באורך [N/X], ולכן סך הכל יעילות של שלב תהיה X * יעילות של איחוד לרשימה באורך [N/X], ולכן [X*[N/X, ולכן N. מספר השלבים במיון יהיה LogN, שכן בכל שלב נישאר עם חצי ממספר הרשימות שאיתן התחלנו את השלב, ונסיים כשנשאר עם רשימה אחת.

סך כל היעילות יהיה לכן LogN שלבים * (O(N פעולות לשלב, ולכן: (O(N*LogN.

פסאודו-קוד

mergesort(L) 
   if length(L) < 2
      return L 
   else 
      split L into lists L1 and L2, each of n/2 elements 
      L1 = mergesort(L1)
      L2 = mergesort(L2) 
      return merge(L1,L2) 
   endif

כאשר הפונקציה merge מאחדת שתי רשימות ממוינות. קל יותר להבין את הפונקציה כאשר מאחדים שתי מחסניות ממוינות:

Merge(S1, S2)
{ 
   repeat until S1 or S2 is empty
   { 
      v1 = pop(S1)
      v2 = pop(S2)
      output(min(v1,v2))
      if (max(v1,v2) = v1) then
         push v1 onto S1
      else 
         push v2 onto S2
      endif
   }
   output the remaining nonempty stack by popping its
      values into the output stream
}