والنوع الكبير هو خوارزمية فرز شعبية قائمة على المقارنة معروفة لكفاءتها وأدائها القابل للتنبؤ، ويمكن فهم كيفية حساب عدد المقارنات التي تجريها أن يساعد على تحقيق أقصى قدر من التنفيذ وتحليل أدائها في سيناريوهات مختلفة.

المفهوم الأساسي للدمج

ويقسم النوع الكبير مجموعة إلى أشعة فرعية أصغر، ويصنف كل أشعة فرعية، ثم يدمجها معا، وتشمل العملية الأساسية مقارنة العناصر أثناء عملية الدمج، التي تحدد العدد الإجمالي للمقارنات التي أجريت.

حساب المقارنات أثناء الاندماج

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

تقدير مجموع المقارنات

ويمكن تقريب العدد الإجمالي للمقارنات في نوع كبير عن طريق تحليل كل عملية متكاملة على جميع مستويات التكرار، وبالنسبة لمجموعة من الحجم n ، فإن المقارنات الإجمالية هي تقريبا:

  • n log2 n] in the average and worst case.
  • ويشمل كل مستوى من مستويات التكرار دمج الأشعة دون الإقليمية، مع إجراء مقارنات إجمالية على جميع المستويات.
  • ويضاعف عدد المقارنات لكل مستوى مع ازدياد عدد الأشعة دونية.

طريقة الحساب العملي

وحساب المقارنات عمليا، محاكاة العملية الدمجية أو استخدام العلاقة التصحيحية:

C(n) = C( ⁇ n/2 ⁇ ) + C(n/2 ⁇ ) + (n - 1)]

(أ) إذا كانت C(n)] هي المقارنات الإجمالية لمجموعة من الحجم n . وتُحسب هذه الصيغة التصحيحية للمقارنات في الأشعة دونية وأثناء الاندماج.