מיון מיזוג

מיון מיזוג (באנגלית: Merge Sort) הוא אלגוריתם מיון רקורסיבי קל למימוש המתבסס על קלות מיזוגם של מערכים ממוינים.
סיבוכיות זמן ריצה: . סיבוכיות זיכרון:

תיאור האלגוריתם

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

דוגמה למימוש בשפת C++

#include <iostream>#include <time.h>using namespace std;const int ARR_LENGTH = 1000;void merge (int arr [], int temp [], int left, int mid, int right){
int leftPlace = left, rightPlace = mid +1;
bool leftOver = false,//all the left data was merged
 rightOver = false;//all the right data was merged


for  (int place = left; place <= right; place++)
{
if (leftPlace > mid) leftOver = true;
if (rightPlace > right) rightOver = true;

temp [place] = (rightOver || !leftOver && arr [leftPlace] <= arr [rightPlace])?//the merge
arr [leftPlace ++] : arr [rightPlace ++];
}
for (int i = left; i <= right; i++)//return the merged data into the array
arr [i] = temp [i];}void mergeSort (int arr [], int temp [], int left, int right){
int mid = (right + left) /2;

if (mid > left)//more than one cell
mergeSort (arr, temp, left, mid);

if (right > mid +1)//more than one cell
mergeSort (arr, temp, mid +1, right);

merge (arr, temp, left, mid, right);}
 
void sort (int arr []){
int temp [ARR_LENGTH];//array aid

mergeSort (arr, temp, 0, ARR_LENGTH -1);}int main(){
srand ( (unsigned int) (time(NULL)));//init the rand

int arr [ARR_LENGTH];

for (int i =0; i < ARR_LENGTH; i++)
 arr [i] = rand () % 100;//insert data

for (int i =0; i < ARR_LENGTH; i++)
cout << arr [i] << " ";//print before sorting
cout << endl << endl;

sort (arr);

for (int i =0; i < ARR_LENGTH; i++)
cout << arr [i] << " ";//print after sorting
cout << endl;

return (EXIT_SUCCESS);}

דוגמה למימוש בשפת C

#include<stdio.h>#define MAX 100void mergeSort(int arr[], int low, int mid, int high);void partition(int arr[], int low, int high);int main(){

int merge[MAX] = { 0 };
int i = 0;
unsigned int n = 0;

printf("Enter the total number of elements: ");
scanf("%u", &n);

printf("Enter the elements which to be sort: ");
for (i = 0; i < n; i++)
{
scanf("%d", &merge[i]);
}

partition(merge, 0, n - 1);

printf("After merge sorting elements are: ");
for (i = 0; i < n; i++)
{
printf("%d ", merge[i]);
}
system("PAUSE");
return 0;}void partition(int arr[], int low, int high){
int mid = 0;

if (low < high)
{
mid = (low + high) / 2;
partition(arr, low, mid);
partition(arr, mid + 1, high);
mergeSort(arr, low, mid, high);
}}void mergeSort(int arr[], int low, int mid, int high){
int i = 0;
int m = 0;
int k = 0;
int l = 0;
int temp[MAX];

l = low;
i = low;
m = mid + 1;

while ((l <= mid) && (m <= high))
{
if (arr[l] <= arr[m])
{
temp[i] = arr[l];
l++;
}
else
{
temp[i] = arr[m];
m++;
}
i++;
}

if (l > mid)
{
for (k = m; k <= high; k++)
{
temp[i] = arr[k];
i++;
}
}
else
{
for (k = l; k <= mid; k++)
{
temp[i] = arr[k];
i++;
}
}

for (k = low; k <= high; k++)
{
arr[k] = temp[k];
}}

דוגמה למימוש בשפת python 3

def mergeSort(alist):
    print("Splitting ",alist)
    if len(alist)>1:
        mid = len(alist)//2
        lefthalf = alist[:mid]
        righthalf = alist[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        i=0
        j=0
        k=0
        while i < len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k]=lefthalf[i]
                i=i+1
            else:
                alist[k]=righthalf[j]
                j=j+1
            k=k+1

        while i < len(lefthalf):
            alist[k]=lefthalf[i]
            i=i+1
            k=k+1

        while j < len(righthalf):
            alist[k]=righthalf[j]
            j=j+1
            k=k+1
    print("Merging ",alist)alist = [54,26,93,17,77,31,44,55,20]mergeSort(alist)print(alist)

דוגמת הרצה

השרטוט הבא מדגים כיצד ממיין האלגוריתם מערך בגודל 7 המכיל את הערכים: 38,27,43,3,9,82,10.

ניתוח סיבוכיות מיון-מיזוג

ניתן לשים לב שפעולת ה"מיון" אינה באמת מתרחשת, פעולה זו פשוט קוראת לפונקציה מחדש. הפעולה היחידה המתרחשת בפועל היא פעולת המיזוג. קל לחשב את סיבוכיות זמן הריצה של פעולה זו, בכל סיבוב של המיזוג אנו מכניסים איבר אחד למערך, סה"כ, משום שקיימים  איברים, אנו מבצעים  פעולות. כעת נותר לנו לחשב כמה פעמים פעולה זו מתבצעת, ובכל פעם לבדוק כמה איברים משתתפים בפעולה.
ננסה לחשב תחילה את מספר הפעמים שמתבצעת פעולת המיזוג. הפעולה מתבצעת בכל קריאה לפונקציה "מיון-מיזוג". הקריאה הראשונה תמזג בין שני חצאי מערכים בגודל  (סה"כ  איברים, סיבוכיות זמן ריצה . לפני-כן הקריאה הראשונה קוראת פעמיים למיון-מיזוג, פעם אחת עבור חצי המערך הראשון ופעם שנייה עבור חצי המערך השני. בכל קריאה יתבצע מיזוג של שני חצאי מערכים בגודל , סה"כ מדובר ב-4 מערכים ולכן יש סה"כ  איברים שיתמזגו ושוב סיבוכיות זמן הריצה הכוללת היא . האלגוריתם ימשיך עד אשר כל המערכים יהיו בגודל 1 ואז נמזג אותם זוג-זוג, עדיין מדובר ב- איברים ולכן סיבוכיות זמן הריצה של כל פעולות המיזוג יחד היא .
בשלב זה מומלץ בחום להסתכל על השרטוט המופיע בדוגמת ההרצה שכן הוא מיטיב להסביר את הנאמר לעיל.
נסתכל בכל פעם רק על חלק אחד של המערך המפוצל, נתחיל במערך הגדול ונשאר עם מערך בגודל  ואז נמשיך להתבונן במערך בגודל  וכן הלאה, עד אשר נגיע למערך בגודל 1. בכל שלב מתבצע מיזוג שזמן ריצתו , נותר רק לספור כמה שלבים כאלו יש.
כפי שנאמר קודם, בכל פעם אנו שולחים למיון-מיזוג מערך שגודלו חצי מהמערך הקודם. לאחר קריאה אחת יהיה גודל המערך , לאחר שתי קריאות יהיה גודלו  וכן הלאה. התהליך ייגמר כאשר גודל המערך הוא 1. אם התהליך כולו יימשך  פעמים, יהיה גודל המערך . אנו דורשים שגודל זה יהיה 1 ולכן נדרוש . נוציא  משני אגפי המשוואה ונקבל כי  .
קבלנו שמתרחשות  פעולות מיזוג שסיבוכיות זמן הריצה של כל אחת מהן היא .
סה"כ סיבוכיות זמן הריצה של האלגוריתם היא, אם כן, .
קיימת גם גרסה מקבילית של האלגוריתם המשתמשת ב  מעבדים ופועלת בסיבוכיות של .