فرز الدمج

فرز الدمج (يُكتب أيضًا mergesort أو merge-sort ^{[ 2 ]} ) هو خوارزمية فرز فعّالة وعامة الأغراض تعتمد على المقارنة . معظم تطبيقات فرز الدمج مستقرة ، أي أن الترتيب النسبي للعناصر المتساوية يبقى نفسه بين المدخلات والمخرجات. فرز الدمج هو خوارزمية فرق تسد، ابتكرها جون فون نيومان عام 1945. ^{[ 3 ]} وقد نُشر وصف وتحليل مفصلان لفرز الدمج من الأسفل إلى الأعلى في تقرير لجولدستاين وفون نيومان في وقت مبكر من عام 1948. ^{[ 4 ]}

من الناحية النظرية، تعمل عملية فرز الدمج على النحو التالي:

1. قسّم القائمة غير المرتبة إلى n قائمة فرعية، تحتوي كل منها على عنصر واحد (تعتبر القائمة التي تحتوي على عنصر واحد مرتبة).
2. قم بدمج القوائم الفرعية بشكل متكرر لإنتاج قوائم فرعية جديدة مرتبة حتى يتبقى لديك قائمة فرعية واحدة فقط. ستكون هذه هي القائمة المرتبة.

تعتبر عملية فرز الدمج فعالة لأنه يمكن إجراء دمج وفرز قائمتين فرعيتين في وقت خطي، بشرط أن تكون القوائم الفرعية مرتبة بالفعل.

// نسخ جزء من المصفوفة a إلى المصفوفة b (من البداية إلى النهاية - 1) void copyArray ( int [] a , int begin , int end , int [] b ) { for ( int k = begin ; k < end ; ++ k ) { b [ k ] = a [ k ] ; } }// دمج نصفين مرتبين (من a) في سلسلة مرتبة واحدة (في b) void topDownMerge ( int [] a , int begin , int middle , int end , int [] b ) { int i = begin ; int j = middle ;// دمج المجموعتين المرتبتين في b for ( int k = begin ; k < end ; ++ k ) { if ( i < middle && ( j >= end || a [ i ] <= a [ j ] )) { b [ k ] = a [ i ] ; // أخذ عنصر من المجموعة اليسرى i ++ ; } else { b [ k ] = a [ j ] ; // أخذ عنصر من المجموعة اليمنى j ++ ; } } }// قسّم المصفوفة a إلى نصفين، ورتّب كلا النصفين في b، // ثم ادمج النصفين المرتبين مرة أخرى في a void topDownSplitMerge ( int [] a , int begin , int end , int [] b ) { if ( end - begin <= 1 ) { return ; // الحالة الأساسية: حجم التشغيل هو 1، لذا فهو مرتب بالفعل }int middle = ( begin + end ) / 2 ; // إيجاد نقطة المنتصف لتقسيم المصفوفة// فرز النصفين الأيسر والأيمن بشكل متكرر في b topDownSplitMerge ( b , begin , middle , a ); topDownSplitMerge ( b , middle , end , a );// دمج النصفين المرتبين مرة أخرى في دالة topDownMerge ( b , begin , middle , end , a ); }void topDownMergeSort ( int [] a , int [] b , int n ) { // نسخ المصفوفة a بالكامل إلى b مبدئيًا copyArray ( a , 0 , n , b ); // تقسيم ودمج المصفوفة b بشكل متكرر في a topDownSplitMerge ( a , 0 , n , b ); }

// نسخ المصفوفة b إلى المصفوفة a void copyArray ( int [] b , int [] a , int n ) { for ( int i = 0 ; i < n ; i ++ ) { a [ i ] = b [ i ] ; } }// الجزء الأيسر هو a[left : right-1]. // الجزء الأيمن هو a[right : end-1]. void bottomUpMerge ( int [] a , int left , int right , int end , int [] b ) { int i = left ; int j = right ;// طالما توجد عناصر في السلاسل اليسرى أو اليمنى... for ( int k = left ; k < end ; ++ k ) { // إذا كان رأس السلسلة اليسرى موجودًا وكان أصغر من أو يساوي رأس السلسلة اليمنى الموجودة. if ( i < right && ( j >= end || a [ i ] <= a [ j ] )) { b [ k ] = a [ i ] ; i = i + 1 ; } else { b [ k ] = a [ j ] ; j = j + 1 ; } } }void bottomUpMergeSort ( int [] a , int [] b , int n ) { // كل مجموعة من عنصر واحد في a مُرتبة بالفعل. // أنشئ مجموعات مُرتبة أطول تدريجيًا بأطوال 2، 4، 8، 16... حتى يتم ترتيب المصفوفة بأكملها. for ( int width = 1 ; width < n ; width *= 2 ) { // المصفوفة a مليئة بمجموعات بطول width. for ( int i = 0 ; i < n ; i = i + 2 * width ) { // ادمج مجموعتين: a[i:i+width-1] و a[i+width:i+2*width-1] في b[] // أو انسخ a[i:n-1] إلى b[] (if (i+width >= n)) bottomUpMerge ( a , i , Math . min ( i + width , n ), Math . min ( i + 2 * width , n ), b ); } // الآن، مصفوفة العمل b مليئة بسلاسل طولها 2 * عرضها. // انسخ المصفوفة b إلى المصفوفة a للتكرار التالي. // سيكون التنفيذ الأكثر كفاءة هو تبديل أدوار a و b. copyArray ( b , a , n ); } }

دالة merge_sort( list m) هي // الحالة الأساسية. يتم فرز قائمة تحتوي على صفر أو عنصر واحد، بحكم التعريف. إذا كان طول m ≤ 1، فسيتم إرجاع m // حالة تكرارية. أولاً، قسّم القائمة إلى قوائم فرعية متساوية الحجم // تتكون من النصف الأول والنصف الثاني من القائمة. // يفترض هذا أن القوائم تبدأ من الفهرس 0. var left := قائمة فارغة var right := قائمة فارغة for each x with index i in m do if i < (length of m)/2 then أضف x إلى اليسار آخر أضف x إلى اليمين // فرز القائمتين الفرعيتين بشكل متكرر. left := merge_sort(left) right := merge_sort(right) // ثم ادمج القوائم الفرعية التي تم فرزها الآن. أعد دمج (اليسار، اليمين)

دالة merge(left, right) هي var result := قائمة فارغة طالما أن اليسار ليس فارغًا واليمين ليس فارغًا، إذا كان أول عنصر في اليسار أقل من أو يساوي أول عنصر في اليمين، أضف أول (يسار) إلى النتيجة left := rest(left) آخر أضف أول (يمين) إلى النتيجة يمين := باقي(يمين) // قد تحتوي القائمة اليسرى أو اليمنى على عناصر؛ استهلكها. // (سيتم الدخول إلى حلقة واحدة فقط من الحلقات التالية.) طالما أن القائمة اليسرى غير فارغة، نفّذ أضف أول (يسار) إلى النتيجة left := rest(left) طالما أن اليمين ليس فارغًا، نفّذ أضف أول (يمين) إلى النتيجة يمين := باقي(يمين) إرجاع النتيجة

دالة merge_sort( رأس العقدة ) هي // إرجاع إذا كانت القائمة فارغة إذا كان رأس المصفوفة يساوي nil، فأرجع nil. المتغير node هو مصفوفة من 32 عنصرًا؛ جميعها فارغة في البداية. المتغير node هو نتيجة العملية . المتغير node هو العنصر التالي . المتغير i هو عدد صحيح . النتيجة := رأس // دمج العقد في مصفوفة طالما أن النتيجة لا تساوي صفرًا، نفّذ next := result.next; result.next := nil for (i = 0; (i < 32) && (array[i] ≠ nil); i += 1) do result := merge(array[i], result) array[i] := nil // لا تتجاوز نهاية المصفوفة إذا كانت قيمة i تساوي 32، i -= 1 array[i] := result النتيجة := التالي // دمج المصفوفة في قائمة واحدة النتيجة := لا شيء for (i = 0; i < 32; i += 1) do result := merge(array[i], result) إرجاع النتيجة

mergeSort :: Ord a => [ a ] ​​-> [ a ] ​​mergeSort [] = [] mergeSort [ x ] = [ x ] mergeSort xs = merge ( mergeSort l , mergeSort r ) where ( l , r ) = splitAt ( length xs ` div ` 2 ) xsدمج :: Ord a => ([ a ], [ a ]) -> [ a ] دمج ( [] , xs ) = xs دمج ( xs , [] ) = xs دمج ( x : xs , y : ys ) | x <= y = x : دمج ( xs , y : ys ) | خلاف ذلك = y : دمج ( x : xs , ys )

عند فرز n عنصرًا، يكون متوسط ​​أداء خوارزمية الفرز بالدمج، وكذلك أسوأ أداء لها، O ( n  log n ) مقارنة. إذا كان زمن تشغيل (عدد المقارنات) الفرز بالدمج لقائمة طولها n هو T ( n )، فإن العلاقة التكرارية T ( n ) = 2T ( n / 2) + n تُستنتج من تعريف الخوارزمية (تطبيق الخوارزمية على قائمتين نصف حجم القائمة الأصلية، وجمع n خطوة اللازمة لدمج القائمتين الناتجتين). ^{[ 5 ]} ويُستنتج الشكل المغلق من النظرية الرئيسية للعلاقات التكرارية في أسلوب فرق تسد . 

يُحدد عدد المقارنات التي تُجريها خوارزمية فرز الدمج في أسوأ الحالات بواسطة أرقام الفرز . هذه الأرقام تساوي أو تقل قليلاً عن ( ⌈lg n⌉ − 2⌈lg n⌉ + 1)، وهو ما يقع بين (nlg n − n + 1) و(nlg n + n +  O ( ^{lg n )} ) . [ 6 ] تستغرق خوارزمية فرز الدمج في أفضل حالاتها نصف عدد التكرارات ^{تقريبًا مقارنةً بأسوأ} حالاتها . ^{[ 7 ]}       

بالنسبة لقيم n الكبيرة وقائمة إدخال مرتبة عشوائياً، يقترب العدد المتوقع (المتوسط) للمقارنات في خوارزمية فرز الدمج من α · n أقل من أسوأ حالة، حيث${\displaystyle \alpha =-1+\sum _{k=0}^{\infty }{\frac {1}{2^{k}+1}}\approx 0.2645.}$

في أسوأ الأحوال، يستخدم فرز الدمج ما يقارب 39% مقارنات أقل من فرز السرعة في حالته المتوسطة ، ومن حيث عدد الحركات، فإن تعقيد فرز الدمج في أسوأ الأحوال هو O ( n  log n ) - وهو نفس تعقيد فرز السرعة في أفضل الأحوال. ^{[ 7 ]} 

يُعدّ فرز الدمج أكثر كفاءة من فرز السرعة لبعض أنواع القوائم إذا كان الوصول إلى البيانات المراد فرزها يتم بكفاءة فقط بالتسلسل، ولذا فهو شائع في لغات مثل ليسب ، حيث تكثر هياكل البيانات التي يتم الوصول إليها بالتسلسل. وعلى عكس بعض تطبيقات فرز السرعة (الفعّالة)، يُعدّ فرز الدمج فرزًا مستقرًا.

إن أكثر تطبيقات فرز الدمج شيوعًا لا تقوم بالفرز في مكانها؛ ^{[ 8 ]} لذلك، يجب تخصيص حجم الذاكرة للإدخال لتخزين الإخراج المصنف فيه (انظر أدناه للاختلافات التي تحتاج فقط إلى n /2 مساحة إضافية).

يُشبه فرز الدمج الطبيعي فرز الدمج التصاعدي، باستثناء أنه يستغل أي تسلسلات مُرتبة موجودة بشكل طبيعي في المدخلات. يمكن استغلال كل من التسلسلات الرتيبة والثنائية (المتناوبة صعودًا وهبوطًا)، حيث تُعد القوائم (أو ما يُعادلها من أشرطة أو ملفات) هياكل بيانات ملائمة (تُستخدم كطوابير FIFO أو مكدسات LIFO ). ^{[ 9 ]} في فرز الدمج التصاعدي، تفترض نقطة البداية أن كل تسلسل يتكون من عنصر واحد. عمليًا، تحتوي بيانات الإدخال العشوائية على العديد من التسلسلات القصيرة التي تصادف أنها مُرتبة. في الحالة النموذجية، قد لا يحتاج فرز الدمج الطبيعي إلى العديد من عمليات المرور نظرًا لوجود عدد أقل من التسلسلات المراد دمجها. في أفضل الأحوال، تكون المدخلات مُرتبة بالفعل (أي أنها تسلسل واحد)، لذا يحتاج فرز الدمج الطبيعي إلى المرور مرة واحدة فقط على البيانات. في العديد من الحالات العملية، توجد تسلسلات طبيعية طويلة، ولهذا السبب يُستغل فرز الدمج الطبيعي كمكون رئيسي في Timsort . مثال:

البداية: 3 4 2 1 7 5 8 9 0 6 اختر التسلسلات: (3 4)(2)(1 7)(5 8 9)(0 6) دمج: (2 3 4)(1 5 7 8 9)(0 6) دمج: (1 2 3 4 5 7 8 9)(0 6) دمج: (0 1 2 3 4 5 6 7 8 9)

يُقال رسميًا أن فرز الدمج الطبيعي هو الأمثل من حيث Runs ، حيث${\displaystyle {\mathtt {يجري}}(L)}$هو عدد مرات الركض في${\displaystyle L}$ناقص واحد.

تُستخدم عمليات فرز الاختيار البديلة في البطولات لجمع عمليات التشغيل الأولية لخوارزميات الفرز الخارجية.

بدلاً من دمج كتلتين في كل مرة، يدمج دمج بينغ بونغ أربع كتل في كل مرة. تُدمج الكتل الأربع المُرتّبة في وقت واحد في مساحة إضافية لتكوين كتلتين مُرتّبتين، ثم تُدمج الكتلتان المُرتّبتان مرة أخرى في الذاكرة الرئيسية. يُلغي هذا الأسلوب عملية النسخ ويُقلل إجمالي عدد عمليات النقل إلى النصف. كان برنامج WikiSort في عام 2014 من أوائل البرامج المجانية التي طبّقت دمج أربع كتل في وقت واحد، ووُصفت هذه الطريقة لاحقًا في نفس العام بأنها تحسين لفرز الصبر، وسُمّيت بدمج بينغ بونغ. ^{[ 10 ] [ 11 ]} طبّق برنامج Quadsort هذه الطريقة في عام 2020 وأطلق عليها اسم دمج رباعي. ^{[ 12 ]}

من عيوب خوارزمية فرز الدمج، عند تطبيقها على المصفوفات، متطلباتها العالية من الذاكرة العاملة (O ( n )) . وقد اقتُرحت عدة طرق لتقليل الذاكرة أو لجعل فرز الدمج يعمل بشكل كامل في مكانه .

• اقترح كرونرود (1969) نسخة بديلة من فرز الدمج تستخدم مساحة إضافية ثابتة.
• يقدم كاتاجاينن وآخرون خوارزمية تتطلب مقدارًا ثابتًا من ذاكرة العمل: مساحة تخزين كافية لحفظ عنصر واحد من مصفوفة الإدخال، ومساحة إضافية لحفظ O (1) مؤشرًا في مصفوفة الإدخال. وقد حققوا حدًا زمنيًا قدره O ( n log n ) باستخدام ثوابت صغيرة، لكن خوارزميتهم غير مستقرة. ^{[ 13 ]}
• بُذلت عدة محاولات لإنتاج خوارزمية دمج موضعي يمكن دمجها مع فرز الدمج القياسي (من أعلى إلى أسفل أو من أسفل إلى أعلى) لإنتاج فرز دمج موضعي. في هذه الحالة، يمكن توسيع مفهوم "الدمج الموضعي" ليشمل "استخدام مساحة مكدس لوغاريتمية"، لأن فرز الدمج القياسي يتطلب هذه المساحة لاستخدامه الخاص في المكدس. وقد أظهر جيفرت وآخرون إمكانية الدمج الموضعي المستقر في زمن قدره O ( n log n ) باستخدام مساحة تخزين مؤقتة ثابتة ، إلا أن خوارزميتهم معقدة ولها عوامل ثابتة عالية: إذ قد يستغرق دمج مصفوفات بطول n و m عدد 5n + 12m + o ( m ) من الحركات. ^{[ 14 ]} تم تبسيط هذه الخوارزمية المعقدة ذات العوامل الثابتة العالية وجعلها أسهل للفهم. قدم بينغ تشاو هوانغ ومايكل أ. لانغستون [ ^{15 ] خوارزمية} دمج موضعي عملية وبسيطة ذات زمن خطي لدمج قائمة مرتبة باستخدام مساحة إضافية ثابتة. وقد استند كلاهما إلى أعمال كرونرود وآخرين. تُدمج هذه الخوارزمية البيانات في زمن خطي وبمساحة إضافية ثابتة. يستغرق متوسط ​​وقتها وقتًا أطول بقليل من خوارزميات فرز الدمج القياسية، مع إمكانية استغلال O ( n ) من خلايا الذاكرة الإضافية المؤقتة، بأقل من الضعف. على الرغم من أن الخوارزمية أسرع بكثير عمليًا، إلا أنها غير مستقرة مع بعض القوائم. ولكن باستخدام مفاهيم مشابهة، تمكنوا من حل هذه المشكلة. من بين الخوارزميات الأخرى التي تُدمج البيانات في مكانها خوارزمية SymMerge، التي تستغرق زمنًا إجماليًا قدره O (( n + m ) log( n + m )) وهي مستقرة. ^{[ 16 ]} يؤدي دمج هذه الخوارزمية في فرز الدمج إلى زيادة تعقيدها إلى O ( n (log n ) ^² ) ، وهو تعقيد غير خطي ، ولكنه لا يزال شبه خطي .
• تستخدم العديد من تطبيقات الفرز الخارجي شكلاً من أشكال فرز الدمج حيث يتم تقسيم المدخلات إلى عدد أكبر من القوائم الفرعية، ومن الناحية المثالية إلى عدد يجعل دمجها مجموعة الصفحات التي تتم معالجتها حاليًا تتناسب مع الذاكرة الرئيسية.
• يُعد فرز دمج الكتل أحد المتغيرات الحديثة المستقرة والخطية والداخلية للدمج ، والذي يقوم بإنشاء قسم من القيم الفريدة لاستخدامها كمساحة تبديل.
• يمكن تقليل حجم الذاكرة المستخدمة إلى O ( √n ) باستخدام عمليات البحث الثنائي والتدوير. ^{[ 17 ]} تُستخدم هذه الطريقة في مكتبة STL الخاصة بلغة C++ وخوارزمية الفرز الرباعي. ^{[ 12 ]}
• لتقليل الحاجة إلى نسخ البيانات إلى قوائم متعددة، يمكن ربط حقل معلومات جديد بكل مفتاح (تُسمى العناصر في القائمة m بالمفاتيح). يُستخدم هذا الحقل لربط المفاتيح والمعلومات المرتبطة بها في قائمة مُرتبة (يُسمى المفتاح والمعلومات المرتبطة به سجلاً). بعد ذلك، تتم عملية دمج القوائم المُرتبة بتغيير قيم الروابط؛ دون الحاجة إلى نقل أي سجلات. عادةً ما يكون الحقل الذي يحتوي على رابط فقط أصغر من السجل الكامل، وبالتالي سيستهلك مساحة أقل. هذه تقنية فرز قياسية، ولا تقتصر على فرز الدمج.
• إحدى الطرق البسيطة لتقليل المساحة الإضافية إلى n /2 هي الحفاظ على المصفوفة اليسرى واليمنى كبنية واحدة، ونسخ الجزء الأيسر فقط من m إلى مساحة مؤقتة، وتوجيه دالة الدمج لوضع الناتج المدمج في m . في هذه الحالة، يُفضّل تخصيص المساحة المؤقتة خارج دالة الدمج ، بحيث لا يلزم سوى تخصيص واحد. كما يتم التخفيف من النسخ الزائد المذكور سابقًا، حيث يصبح السطران الأخيران قبل عبارة إرجاع النتيجة (دالة الدمج في الشفرة الزائفة أعلاه) زائدين عن الحاجة.

يُعدّ فرز الدمج الخارجي عمليًا عند استخدام محركات الأقراص أو الأشرطة عندما تكون البيانات المراد فرزها كبيرة جدًا بحيث لا تتسع في الذاكرة . يشرح مصطلح "الفرز الخارجي" كيفية تنفيذ فرز الدمج باستخدام محركات الأقراص. يستخدم فرز الأشرطة النموذجي أربعة محركات أشرطة. جميع عمليات الإدخال والإخراج متسلسلة (باستثناء عمليات إعادة اللف في نهاية كل دورة). يمكن لتطبيق بسيط أن يعمل باستخدام مخزنين مؤقتين للسجلات وعدد قليل من متغيرات البرنامج.

باستخدام تسمية محركات الأشرطة الأربعة بالأحرف A وB وC وD، مع وجود البيانات الأصلية على المحرك A، واستخدام مخزنين مؤقتين فقط، فإن الخوارزمية تشبه التنفيذ التصاعدي ، حيث تستخدم أزواجًا من محركات الأشرطة بدلًا من المصفوفات في الذاكرة. ويمكن وصف الخوارزمية الأساسية كما يلي:

1. دمج أزواج السجلات من A؛ وكتابة قوائم فرعية مكونة من سجلين بالتناوب إلى C و D.
2. ادمج القوائم الفرعية المكونة من سجلين من C و D في قوائم فرعية مكونة من أربعة سجلات؛ واكتب هذه القوائم بالتناوب إلى A و B.
3. ادمج القوائم الفرعية المكونة من أربعة سجلات من A و B في قوائم فرعية مكونة من ثمانية سجلات؛ واكتب هذه القوائم بالتناوب في C و D
4. كرر ذلك حتى تحصل على قائمة واحدة تحتوي على جميع البيانات مرتبة - في log ₂ ( n ) تمريرات.

بدلاً من البدء بسلاسل عمليات قصيرة جدًا، يُستخدم عادةً خوارزمية هجينة ، حيث تقرأ المرحلة الأولى عددًا كبيرًا من السجلات في الذاكرة، ثم تُجري فرزًا داخليًا لإنشاء سلسلة عمليات طويلة، ثم تُوزّع هذه السلاسل الطويلة على مجموعة الإخراج. تُجنّب هذه الخطوة العديد من المراحل الأولية. على سبيل المثال، يُوفّر الفرز الداخلي لـ 1024 سجلًا تسع مراحل. غالبًا ما يكون الفرز الداخلي كبيرًا نظرًا لهذه الفائدة. في الواقع، توجد تقنيات تُمكن من جعل سلاسل العمليات الأولية أطول من الذاكرة الداخلية المتاحة. إحدى هذه التقنيات، وهي "محراث الثلج" لكنوت (المبني على كومة ثنائية دنيا )، تُولّد سلاسل عمليات أطول بمرتين (في المتوسط) من حجم الذاكرة المستخدمة. ^{[ 18 ]}

مع بعض التكاليف الإضافية، يمكن تعديل الخوارزمية المذكورة أعلاه لاستخدام ثلاثة أشرطة. كما يمكن تحقيق زمن تشغيل قدره O ( n log n ) باستخدام طابورين ، أو مكدس وطابور، أو ثلاثة مكدسات. في المقابل، باستخدام k > شريطين (و O ( k ) عنصرًا في الذاكرة)، يمكننا تقليل عدد عمليات الشريط بمقدار O (log k ) مرة باستخدام دمج ثنائي الاتجاه k/2 .

يُعد فرز الدمج متعدد المراحل نوعًا أكثر تطورًا من فرز الدمج الذي يعمل على تحسين استخدام محرك الأقراص الشريطية (ومحرك الأقراص الصلبة) .

في الحواسيب الحديثة، تُعدّ خاصية "موضعية المرجع" ذات أهمية قصوى في تحسين البرمجيات ، نظرًا لاستخدامها هياكل ذاكرة متعددة المستويات. وقد طُرحت نسخ من خوارزمية فرز الدمج مُراعية لذاكرة التخزين المؤقت، حيث تم اختيار عملياتها خصيصًا لتقليل حركة الصفحات من وإلى ذاكرة التخزين المؤقت للجهاز. على سبيل المثال،تتوقف خوارزمية فرز الدمج المُجزأ عن تقسيم المصفوفات الفرعية عند الوصول إلى مصفوفات فرعية بحجم S، حيث S هو عدد عناصر البيانات التي تتسع لها ذاكرة التخزين المؤقت لوحدة المعالجة المركزية. تُفرز كل مصفوفة فرعية من هذه المصفوفات باستخدام خوارزمية فرز موضعي، مثلفرز الإدراج، للحد من عمليات تبديل الذاكرة، ثم يُستكمل فرز الدمج العادي بالطريقة التكرارية القياسية. وقد أظهرت هذه الخوارزمية أداءً أفضلعلى الأجهزة التي تستفيد من تحسين ذاكرة التخزين المؤقت.(لاماركا ولادنر ، 1997)

تتميز خوارزمية فرز الدمج بقدرتها العالية على التوازي بفضل استخدامها لأسلوب فرق تسد . وقد طُوّرت على مر السنين عدة نسخ متوازية مختلفة من هذه الخوارزمية. بعض خوارزميات فرز الدمج المتوازية ترتبط ارتباطًا وثيقًا بخوارزمية الدمج التسلسلي من أعلى إلى أسفل، بينما تتميز خوارزميات أخرى ببنية عامة مختلفة وتستخدم أسلوب الدمج متعدد الاتجاهات (K-way merge ).

// فرز العناصر من lo إلى hi (باستثناء) من المصفوفة A. خوارزمية mergesort(A, lo, hi) هي إذا كان lo+1 < hi ثم // عنصران أو أكثر. mid := ⌊(lo + hi) / 2⌋ fork mergesort(A, lo, mid) mergesort(A, mid, hi) join merge(A, lo, mid, hi)

/** * أ: مصفوفة الإدخال * ب: مصفوفة الإخراج * lo: الحد الأدنى * hi: الحد الأعلى * إيقاف: إزاحة */ خوارزمية الفرز بالدمج المتوازي (A، lo، hi، B، off) هي الطول := أعلى - أدنى + 1 إذا كان الطول يساوي 1، فإن  B[off] := A[lo]، وإلا فليكن T[1..len] مصفوفة جديدة mid := ⌊(lo + hi) / 2⌋ mid' := mid - lo + 1 fork parallelMergesort(A, lo, mid, T, 1) parallelMergesort(A, mid + 1, hi, T, mid' + 1) join parallelMerge(T, 1, mid', mid' + 1, len, B, off)

فرز الدمج متعدد الاتجاهات المتوازي

يبدو من التعسف حصر خوارزميات فرز الدمج في طريقة الدمج الثنائي، نظرًا لوجود عدد أكبر من المعالجات (p > 2) عادةً. قد يكون من الأفضل استخدام طريقة الدمج متعدد الاتجاهات (K-way merge method)، وهي تعميم للدمج الثنائي، حيث${\displaystyle k}$يتم دمج التسلسلات المصنفة. يُعد هذا النوع من الدمج مناسبًا تمامًا لوصف خوارزمية فرز على ذاكرة الوصول العشوائي المبرمجة (PRAM) . ^{[ 21 ] [ 22 ]}

الفكرة الأساسية

بافتراض وجود سلسلة غير مرتبة من${\displaystyle n}$العناصر، والهدف هو فرز التسلسل باستخدام${\displaystyle p}$المعالجات المتاحة . تُوزع هذه العناصر بالتساوي بين جميع المعالجات وتُرتب محليًا باستخدام خوارزمية فرز تسلسلي . وبالتالي، يتكون التسلسل من تسلسلات مرتبة.${\displaystyle S_{1},...,S_{p}}$من الطول${\textstyle \lceil {\frac {n}{p}}\rceil }$لتبسيط الأمر، دع${\displaystyle n}$أن يكون من مضاعفات${\displaystyle p}$، لهذا السبب${\textstyle \left\vert S_{i}\right\vert ={\frac {n}{p}}}$ل${\displaystyle i=1,...,p}$.

ستُستخدم هذه التسلسلات لإجراء عملية اختيار/تقسيم متعددة التسلسلات.${\displaystyle j=1,...,p}$تحدد الخوارزمية عناصر التقسيم${\displaystyle v_{j}}$مع تصنيف عالمي${\textstyle k=j{\frac {n}{p}}}$ثم المواضع المقابلة لـ${\displaystyle v_{1},...,v_{p}}$في كل تسلسل${\displaystyle S_{i}}$يتم تحديدها باستخدام البحث الثنائي ، وبالتالي${\displaystyle S_{i}}$وتنقسم كذلك إلى${\displaystyle p}$التسلسلات الفرعية${\displaystyle S_{i,1},...,S_{i,p}}$مع${\textstyle S_{i,j}:=\{x\in S_{i}|rank(v_{j-1})<rank(x)\leq rank(v_{j})\}}$.

علاوة على ذلك، فإن عناصر${\displaystyle S_{1,i},...,S_{p,i}}$يتم تخصيصها للمعالج${\displaystyle i}$، يعني جميع العناصر بين الرتبة${\textstyle (i-1){\frac {n}{p}}}$والرتبة${\textstyle i{\frac {n}{p}}}$والتي يتم توزيعها على جميع${\displaystyle S_{i}}$وبالتالي، يتلقى كل معالج سلسلة من التسلسلات المرتبة. وحقيقة أن الرتبة${\displaystyle k}$من عناصر التقسيم${\displaystyle v_{i}}$تم اختيارها عالمياً، وتوفر خاصيتين مهمتين: من ناحية،${\displaystyle k}$تم اختيارها بحيث يمكن لكل معالج أن يظل يعمل على${\textstyle n/p}$يتم توزيع العناصر بعد التخصيص. الخوارزمية متوازنة الأحمال بشكل مثالي . من ناحية أخرى، جميع العناصر على المعالج${\displaystyle i}$تكون أقل من أو تساوي جميع العناصر الموجودة على المعالج${\displaystyle i+1}$وبالتالي، يقوم كل معالج بإجراء عملية دمج متعددة الاتجاهات محليًا، ويحصل بذلك على تسلسل مُرتب من تسلسلاته الفرعية. وبفضل هذه الخاصية الثانية، لا حاجة لإجراء عملية دمج متعددة الاتجاهات أخرى ، بل يكفي تجميع النتائج وفقًا لرقم المعالج.

اختيار التسلسل المتعدد

في أبسط صورها، بالنظر إلى${\displaystyle p}$التسلسلات المصنفة${\displaystyle S_{1},...,S_{p}}$موزعة بالتساوي على${\displaystyle p}$المعالجات والرتبة${\displaystyle k}$، المهمة هي إيجاد عنصر${\displaystyle x}$بتصنيف عالمي${\displaystyle k}$في اتحاد المتتاليات. ومن ثم، يمكن استخدام هذا لتقسيم كل منها${\displaystyle S_{i}}$في جزأين عند مؤشر التقسيم${\displaystyle l_{i}}$، حيث يحتوي الجزء السفلي فقط على عناصر أصغر من${\displaystyle x}$بينما العناصر الأكبر من${\displaystyle x}$تقع في الجزء العلوي.

تُعيد الخوارزمية التسلسلية المعروضة مؤشرات الانقسامات في كل تسلسل، على سبيل المثال المؤشرات${\displaystyle l_{i}}$في التسلسلات${\displaystyle S_{i}}$بحيث${\displaystyle S_{i}[l_{i}]}$يحتل مرتبة عالمية أقل من${\displaystyle k}$و${\displaystyle \mathrm {rank} \left(S_{i}[l_{i}+1]\right)\geq k}$[ ^{23 ]​}

الخوارزمية msSelect(S : مصفوفة من التسلسلات المرتبة [S_1,..,S_p], k : عدد صحيح) هي من أجل i = 1 إلى p (l_i, r_i) = (0, |S_i|-1) طالما يوجد i: l_i < r_i، قم بما يلي : // اختر عنصرًا محوريًا في S_j[l_j]، ...، S_j[r_j]، ثم اختر j عشوائيًا بشكل منتظم v := pickPivot(S, l, r) من أجل i = 1 إلى p m_i = binarySearch(v, S_i[l_i, r_i]) // بالتسلسل إذا كان m_1 + ... + m_p >= k فإن // m_1 + ... + m_p هو الرتبة العالمية لـ v r := m // تعيين متجه آخر ل := م إرجاع l

تم اختيار نموذج PRAM لتحليل التعقيد . إذا كانت البيانات موزعة بالتساوي على جميع${\displaystyle p}$يستغرق تنفيذ طريقة البحث الثنائي (binarySearch) في عملية p-fold مدة تشغيل قدرها${\displaystyle {\mathcal {O}}\left(p\log \left(n/p\right)\right)}$عمق التكرار المتوقع هو${\displaystyle {\mathcal {O}}\left(\log \left(\textstyle \sum _{i}|S_{i}|\right)\right)={\mathcal {O}}(\log(n))}$كما هو الحال في خاصية الاختيار السريع العادية . وبالتالي، فإن إجمالي وقت التشغيل المتوقع هو${\displaystyle {\mathcal {O}}\left(p\log(n/p)\log(n)\right)}$.

عند تطبيق هذه الخوارزمية على فرز الدمج متعدد الاتجاهات المتوازي، يجب استدعاؤها بالتوازي بحيث يتم تطبيقها على جميع عناصر التقسيم ذات الرتبة${\textstyle i{\frac {n}{p}}}$ل${\displaystyle i=1,..,p}$يتم العثور عليها في وقت واحد. ويمكن بعد ذلك استخدام عناصر التقسيم هذه لتقسيم كل تسلسل في${\displaystyle p}$أجزاء، بنفس إجمالي وقت التشغيل لـ${\displaystyle {\mathcal {O}}\left(p\,\log(n/p)\log(n)\right)}$.

الشفرة الزائفة

فيما يلي، نعرض الشفرة الزائفة الكاملة لخوارزمية فرز الدمج متعدد الاتجاهات المتوازية. نفترض وجود تزامن حاجز قبل وبعد اختيار التسلسل المتعدد، بحيث يتمكن كل معالج من تحديد عناصر التقسيم وتقسيم التسلسل بشكل صحيح.

/** * د: مصفوفة غير مرتبة من العناصر * ن: عدد العناصر * p: عدد المعالجات * إرجاع مصفوفة مرتبة */ خوارزمية الفرز المتعدد المتوازي (d : Array, n : int, p : int) هي o := new Array[0, n] // مصفوفة الإخراج for i = 1 to p do in parallel // كل معالج بالتوازي  S_i := d[(i-1) * n/p, i * n/p] // متتالية بطول n/p sort(S_i) // فرز محليًا مزامنة v_i := msSelect([S_1,...,S_p], i * n/p) // العنصر ذو الرتبة العامة i * n/p مزامنة (S_i,1, ..., S_i,p) := sequence_partitioning(si, v_1, ..., v_p) // تقسيم s_i إلى متواليات فرعية o[(i-1) * n/p, i * n/p] := kWayMerge(s_1,i, ..., s_p,i) // دمج وتعيين إلى مصفوفة الإخراج إرجاع o

تحليل

أولاً، يقوم كل معالج بفرز البيانات المخصصة له${\displaystyle n/p}$فرز العناصر محليًا باستخدام خوارزمية فرز ذات تعقيد${\displaystyle {\mathcal {O}}\left(n/p\;\log(n/p)\right)}$بعد ذلك، يجب حساب عناصر التقسيم في الوقت المناسب${\displaystyle {\mathcal {O}}\left(p\,\log(n/p)\log(n)\right)}$وأخيرًا، كل مجموعة من${\displaystyle p}$يجب دمج الأجزاء المنقسمة بالتوازي بواسطة كل معالج في وقت تشغيل قدره${\displaystyle {\mathcal {O}}(\log(p)\;n/p)}$باستخدام خوارزمية دمج متسلسلة من نوع p-way . وبالتالي، يُعطى وقت التشغيل الإجمالي بواسطة

${\displaystyle {\mathcal {O}}\left({\frac {n}{p}}\log \left({\frac {n}{p}}\right)+p\log \left({\frac {n}{p}}\right)\log(n)+{\frac {n}{p}}\log(p)\right)}$.

التكيف والتطبيق العملي

تتميز خوارزمية فرز الدمج متعدد الاتجاهات بقابلية توسع عالية بفضل قدرتها الفائقة على المعالجة المتوازية، مما يسمح باستخدام العديد من المعالجات. وهذا يجعلها خيارًا مناسبًا لفرز كميات هائلة من البيانات، كتلك التي تُعالج في مجموعات الحواسيب . كما أن عيب تعقيد المساحة في فرز الدمج يكاد يكون معدومًا في هذه الأنظمة، نظرًا لأن الذاكرة لا تُمثل عادةً موردًا محدودًا. مع ذلك، تبرز عوامل أخرى في هذه الأنظمة، لا تُؤخذ في الحسبان عند تصميم نموذج PRAM . وهنا، يجب مراعاة الجوانب التالية: التسلسل الهرمي للذاكرة ، عندما لا تتسع البيانات في ذاكرة التخزين المؤقت للمعالجات، أو عبء الاتصال الناتج عن تبادل البيانات بين المعالجات، والذي قد يُصبح عنق زجاجة عندما يتعذر الوصول إلى البيانات عبر الذاكرة المشتركة.

قدم ساندرز وآخرون في ورقتهم البحثية خوارزمية متوازية متزامنة جماعية لفرز الدمج متعدد المستويات ومتعدد الاتجاهات، والتي تقسم${\displaystyle p}$المعالجات إلى${\displaystyle r}$مجموعات من الحجم${\displaystyle p'}$تقوم جميع المعالجات بالفرز محليًا أولًا. على عكس فرز الدمج متعدد الاتجاهات أحادي المستوى، يتم بعد ذلك تقسيم هذه التسلسلات إلى${\displaystyle r}$تُوزَّع الأجزاء على مجموعات المعالجات المناسبة. وتُكرَّر هذه الخطوات بشكل متكرر داخل تلك المجموعات. يُقلِّل هذا من الاتصالات، ويتجنب على وجه الخصوص مشاكل كثرة الرسائل الصغيرة. يُمكن استخدام البنية الهرمية للشبكة الحقيقية الأساسية لتحديد مجموعات المعالجات (مثل الخوادم ، والمجموعات ، ...). ^{[ 22 ]}

على الرغم من أن خوارزمية فرز الكومة لها نفس حدود الوقت لخوارزمية فرز الدمج، إلا أنها تتطلب مساحة إضافية قدرها Θ(1) فقط بدلاً من Θ( n ) التي تتطلبها خوارزمية فرز الدمج. في البنى الحديثة النموذجية، تتفوق تطبيقات الفرز السريع الفعالة عمومًا على خوارزمية فرز الدمج في فرز المصفوفات المخزنة في ذاكرة الوصول العشوائي (RAM). ^{[ 27 ]} يُفضل استخدام الفرز السريع عندما يكون حجم البيانات المراد فرزها صغيرًا، نظرًا لأن تعقيد المساحة للفرز السريع هو O(log n )، مما يساعد في استغلال موضع الذاكرة المؤقتة بشكل أفضل من خوارزمية فرز الدمج (التي تتميز بتعقيد مساحة O(n)). ^{[ 27 ]} من ناحية أخرى، تُعد خوارزمية فرز الدمج خوارزمية فرز مستقرة وأكثر كفاءة في التعامل مع الوسائط التسلسلية بطيئة الوصول. غالباً ما يكون فرز الدمج هو الخيار الأفضل لفرز قائمة مرتبطة : في هذه الحالة، من السهل نسبياً تنفيذ فرز الدمج بطريقة تتطلب فقط مساحة إضافية قدرها Θ(1)، كما أن أداء الوصول العشوائي البطيء للقائمة المرتبطة يجعل بعض الخوارزميات الأخرى (مثل الفرز السريع) تعمل بشكل سيئ، والبعض الآخر (مثل فرز الكومة) مستحيلاً تماماً.

ابتداءً من إصدار بيرل 5.8، أصبح فرز الدمج هو خوارزمية الفرز الافتراضية (كانت خوارزمية الفرز السريع هي المستخدمة في الإصدارات السابقة من بيرل). ^{[ 28 ]} في جافا ، تستخدم دوال Arrays.sort() فرز الدمج أو فرز سريع مُحسَّن حسب أنواع البيانات، ولتحسين كفاءة التنفيذ، يتم التحويل إلى فرز الإدراج عندما يكون عدد عناصر المصفوفة المراد فرزها أقل من سبعة. ^{[ 29 ]} يستخدم نظام لينكس فرز الدمج لقوائمه المتصلة. ^{[ 30 ]}

تُستخدم خوارزمية Timsort ، وهي خوارزمية هجينة مُحسّنة من خوارزميتي فرز الدمج وفرز الإدراج، في مجموعة متنوعة من منصات ولغات البرامج، بما في ذلك منصتي Java و Android ^{[ 31 ]} ، وتستخدمها لغة Python منذ الإصدار 2.3؛ ومنذ الإصدار 3.11، تم تحديث سياسة الدمج في Timsort إلى Powersort . ^{[ 32 ]}

• كورمين، توماس هـ . ليسرسون، تشارلز إي . ريفست، رونالد ل . شتاين، كليفورد (2009) [1990]. مقدمة للخوارزميات (  الطبعة الثالثة). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. رقم ISBN 0-262-03384-4.
• كاتاجاينن، يركي؛ باسانن، تومي؛ تيوهولا، يوكا (1996). "فرز دمج عملي في مكانه" . المجلة الإسكندنافية للحوسبة . 3 (1): 27-40 . CiteSeerX 10.1.1.22.8523 . ISSN 1236-6064 . مؤرشف من الأصل بتاريخ 2011-08-07 . تم الاسترجاع بتاريخ 2009-04-04 .  . أيضًا، فرز الدمج العملي في الموقع . . أيضًا
• كنوت، دونالد (1998). "القسم 5.2.4: الفرز بالدمج". الفرز والبحث . فن برمجة الحاسوب . المجلد  3 (  الطبعة الثانية). أديسون-ويسلي. الصفحات 158-168 . ISBN  0-201-89685-0.
• كرونرود، ماجستير (1969). "خوارزمية الترتيب الأمثل بدون حقل تشغيلي". الرياضيات السوفيتية - دوكلادي . 10 : 744.
• لاماركا، أ.؛ لادنر، ر. إي. (1997). "تأثير الذاكرة المؤقتة على أداء الفرز". وقائع الندوة السنوية الثامنة لجمعية آلات الحوسبة وجمعية الرياضيات الصناعية والتطبيقية حول الخوارزميات المنفصلة (SODA97) : 370-379 . CiteSeerX 10.1.1.31.1153 . 
• سكينا، ستيفن س. (2008). "4.5: فرز الدمج: الفرز بتقسيم البيانات وحلّها". دليل تصميم الخوارزميات (  الطبعة الثانية). سبرينغر. ص 120-125 . ISBN  978-1-84800-069-8.
• شركة صن مايكروسيستمز. "واجهة برمجة تطبيقات المصفوفات (جافا SE 6)" . تم الاطلاع عليه بتاريخ 19-11-2007 .
• شركة أوراكل. "المصفوفات (جافا إس إي 10 وجي دي كي 10)" . تم الاطلاع عليه بتاريخ 23-07-2018 .

• خوارزميات الفرز المتحركة: فرز الدمج على موقع Wayback Machine (مؤرشف في 6 مارس 2015) - عرض توضيحي رسومي
• هياكل البيانات المفتوحة - القسم 11.1.1 - فرز الدمج ، بات مورين
• برنامج بلغة C لتنفيذ خوارزمية فرز الدمج
• كود فرز الدمج باستخدام جافا
• برنامج C++ لفرز الدمج