append first(right) to result
right = rest(right)
if length(left) &gt; 0
append left to result
if length(right) &gt; 0
append right to result
return result
להמחשה, נמזג את קבוצות המספרים הממוינות: 1,2,4,8,9,10,11 ו-3,7.
נראה כעת מהו המערך שהתקבל: 1,2,3,4,7,8,9,10,11. אלו הם בדיוק כל המספרים כאשר הם ממוינים כפי שציפינו.
דוגמה למימוש בשפת.
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 &lt;= right; place++)
if (leftPlace &gt; mid) leftOver = true;
if (rightPlace &gt; right) rightOver = true;
temp [place] = (rightOver || !leftOver &amp;&amp; arr [leftPlace] &lt;= arr [rightPlace])? //the merge
arr [leftPlace ++] : arr [rightPlace ++];
for (int i = left; i &lt;= 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 &gt; left) //more than one cell
mergeSort (arr, temp, left, mid);
if (right &gt; 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 &lt; ARR_LENGTH; i++)
arr [i] = rand () % 100; //insert data
for (int i =0; i &lt; ARR_LENGTH; i++)
cout « arr [i] « " "; //print before sorting
cout « endl « endl;
sort (arr);
for (int i =0; i &lt; ARR_LENGTH; i++)
cout « arr [i] « " "; //print after sorting
cout « endl;
return (EXIT_SUCCESS);
דוגמה למימוש בשפת C.
void 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;
int n = 0;
printf("Enter the total number of elements: ");
scanf("%u", &amp;n);
printf("Enter the elements which to be sort: ");
for (i = 0; i &lt; n; i++)
scanf("%d", &amp;merge[i]);
partition(merge, 0, n - 1);
printf("After merge sorting elements are: ");
for (i = 0; i &lt; n; i++)
printf("%d ", merge[i]);
return 0;
void partition(int arr[], int low, int high)
int mid = 0;
if (low &lt; 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 &lt;= mid) &amp;&amp; (m &lt;= high))
if (arr[l] &lt;= arr[m])
temp[i] = arr[l];
temp[i] = arr[m];
if (l &gt; mid)
for (k = m; k &lt;= high; k++)
temp[i] = arr[k];
for (k = l; k &lt;= mid; k++)
temp[i] = arr[k];
for (k = low; k &lt;= high; k++)
arr[k] = temp[k];
דוגמה למימוש בשפת python 3.
def mergeSort(alist):
print("Splitting ",alist)
if len(alist)&gt;1:
mid = len(alist)//2
lefthalf = alist[:mid]
righthalf = alist[mid:]
mergeSort(lefthalf)
mergeSort(righthalf)
while i &lt; len(lefthalf) and j &lt; len(righthalf):
if lefthalf[i] &lt;= righthalf[j]:
alist[k]=lefthalf[i]
i=i+1
else:
alist[k]=righthalf[j]
j=j+1
k=k+1
while i &lt; len(lefthalf):
alist[k]=lefthalf[i]
i=i+1
k=k+1
while j &lt; 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.
ניתוח סיבוכיות מיון-מיזוג.
פעולת ה"מיון" קוראת לפונקציה מחדש. הפעולה היחידה המתרחשת בפועל היא פעולת המיזוג. קל לחשב את סיבוכיות זמן הריצה של פעולה זו, בכל סיבוב של המיזוג מוכנס איבר אחד למערך, ומשום שקיימים formula_3 איברים, מתבצעות formula_2 פעולות. כעת נותר לחשב כמה פעמים פעולה זו מתבצעת, ובכל פעם לבדוק כמה איברים משתתפים בפעולה.
ננסה לחשב תחילה את מספר הפעמים שמתבצעת פעולת המיזוג. הפעולה מתבצעת בכל קריאה לפונקציה "מיון-מיזוג". הקריאה הראשונה תמזג בין שני חצאי מערכים בגודל formula_7 (סה"כ formula_3 איברים, סיבוכיות זמן ריצה formula_2. לפני-כן הקריאה הראשונה קוראת פעמיים למיון-מיזוג, פעם אחת עבור חצי המערך הראשון ופעם שנייה עבור חצי המערך השני. בכל קריאה יתבצע מיזוג של שני חצאי מערכים בגודל formula_10, סה"כ מדובר ב-4 מערכים ולכן יש סה"כ formula_3 איברים שיתמזגו ושוב סיבוכיות זמן הריצה הכוללת היא formula_2. האלגוריתם ימשיך עד אשר כל המערכים יהיו בגודל 1 ואז נמזג אותם זוג-זוג, עדיין מדובר ב-formula_3 איברים ולכן סיבוכיות זמן הריצה של כל פעולות המיזוג יחד היא formula_2.
נסתכל בכל פעם רק על חלק אחד של המערך המפוצל, נתחיל במערך הגדול ונשאר עם מערך בגודל formula_7 ואז נמשיך להתבונן במערך בגודל formula_10 וכן הלאה, עד אשר נגיע למערך בגודל 1. בכל שלב מתבצע מיזוג שזמן ריצתו formula_17, נותר רק לספור כמה שלבים כאלו יש.
בכל פעם נשלח למיון-מיזוג מערך שגודלו חצי מהמערך הקודם. לאחר קריאה אחת יהיה גודל המערך formula_18, לאחר שתי קריאות יהיה גודלו formula_19 וכן הלאה. התהליך ייגמר כאשר גודל המערך הוא 1. אם התהליך כולו יימשך formula_20 פעמים, יהיה גודל המערך formula_21. כדי שגודל זה יהיה 1 נדרוש formula_22. נוציא formula_23 משני אגפי המשוואה ונקבל כי formula_24.
קבלנו שמתרחשות formula_25 פעולות מיזוג שסיבוכיות זמן הריצה של כל אחת מהן היא formula_2.
סה"כ סיבוכיות זמן הריצה של האלגוריתם היא, אם כן, formula_1.
קיימת גם גרסה מקבילית של האלגוריתם המשתמשת ב formula_28 מעבדים ופועלת בסיבוכיות של formula_29.
אלן גינזברג
Itanium
איטניום
במחשבים, איטניום הוא ארכיטקטורת מיקרומעבד בעל 64 ביט, שפותחה בצוותא על ידי HP ואינטל. מטרתו של איטניום היא ליצור ארכיטקטורה של "עידן הפוסט־RISC" בעלת ביצועים גבוהים, תוך שימוש בתכנון VLIW. מערכת הפקודות הטבעית שלו היא ה־IA-64 החדשה, אך הוא יכול להריץ קוד x86 (בצורה איטית) ובמצב הדמיית קושחה, ובעל אפשרות להגירה של משפחת ה־PA-RISC.
הפרויקט הסתבר בסופו של דבר ככישלון. כיום כמעט רק חברת HP מוכרת מערכות איטניום. הוא לא הצליח להיכנס לשוק הביתי מכיוון שהוא מספק אמולציה איטית יחסית של קוד IA32. עם יציאת ארכיטקטורת AMD64 התברר שיש דרך פשוטה יותר לספק תמיכה במרחב כתובות גדול ועדיין לתמוך בצורה יעילה בקוד הקיים.
בינואר 2019 אינטל הכריזה על הפסקת הפיתוח של סדרת איטניום, כאשר הפסקת התמיכה בהם מתוכננת ליולי 2021.
תכנון.
ברמה הבסיסית, התכנון של איטניום דומה לזה של RISC – ליבת הלוגיקה מכילה סט קטן של הוראות אשר תוכננו לרוץ מהר מאוד. האיטניום משתמש בתכנון אשר מאפשר הרצה של מספר ליבות באופן מקבילי בשביל להשיג מהירות נוספת. הדבר שבו פילוסופיית תכנון האיטניום שונה מ־RISC הוא הצורה שבה ההוראות מועברות ליחידות ליבה אלה.
בתכנון "חוסר־סדר" הרווח, מפענח מורכב בוחן כל הוראה בזמן שהיא עוברת דרך הצינור (pipeline) ורואה איזה מהן יכולה להתבצע במקביל במספר ליבות. למשל בסדרת הוראות שמבצעת codice_1 ו־codice_2 לא תהיה השפעה של ההוראות אחת על השנייה, לכן ניתן להזין אותם לשתי ליבות כדי שירוצו בו זמנית.
ניבוי של איזה קוד יכול להיות מחולק בדרך כזו הוא משימה מורכבת מאוד. במקרים רבים, ערכי הקלט של שורה אחת תלויים בערכי הפלט של שורה אחרת, אך רק אם תנאי מסוים מתקיים. למשל, נסתכל על אותה דוגמה מקודם בשינוי קל:
codice_3. במקרה כזה, החישובים נשארים זהים, אך הפעולה השנייה דורשת את התוצאות של החישוב הראשון כדי לדעת אם יש בכלל צורך בהרצתה.
במקרים כאלה, התוכנית שמובנת במעבד בדרך כלל "מנחשת" איזה מצב יתרחש. ברוב המקרים, פקודת התנאי IF תתבצע, בהנחה שהדוגמה שלנו תבצע ב־90 אחוז מהמקרים את החלק השני שלה, ולכן אפשר בבטחה להזינה לליבה אחרת. אולם, ניחוש מוטעה יכול להביא לירידה ניכרת בביצועים, כיוון שתוצאת החישוב נזרקת והמעבד ממתין לתוצאה הנכונה של החישוב להגיע. חלק גדול משיפור הביצועים במעבדים מודרניים נובע משיפור בלוגיקת החיזוי, אולם בתקופה האחרונה מגמת השיפורים החלה להאט.
במקום זאת, האיטניום מסתמך על המהדר שיבצע משימה זו. עוד לפני שהתוכנית מוזנת למעבד, המהדר מנתח את הקוד ומבצע את אותם סוגים של החלטות אשר היו מתבצעות בזמן ריצה על השבב עצמו. ברגע שהוא החליט איזה נתיבים לבחור, הוא אוסף את כל הפקודות שהוא יודע שניתן להריץ במקביל, אוגד אותם להוראה גדולה יותר בצורה כזו בתוכנית תחת ההגדרה VLIW.