فرز سريع

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

مقتطف من التعليمات البرمجية لحساب متوسط ​​ثلاثة عناصر لتقسيم لوموتو:

mid := ⌊(lo + hi) / 2⌋ إذا كان A[mid] < A[lo] استبدل A[lo] بـ A[mid] إذا كانت A[hi] < A[lo] استبدل A[lo] بـ A[hi] إذا كانت A[mid] < A[hi] استبدل A[mid] بـ A[hi] pivot := A[hi]

يضع الوسيط في A[hi]البداية، ثم يتم استخدام تلك القيمة الجديدة A[hi]للمحور، كما هو الحال في الخوارزمية الأساسية المعروضة أعلاه.

على وجه التحديد، يبلغ العدد المتوقع للمقارنات اللازمة لفرز n عنصرًا (انظر §  تحليل الحالة المتوسطة ) مع اختيار محور عشوائي 1.386 n log n . يُقلل استخدام محور الوسيط الثلاثي هذا العدد إلى C _{n , 2} ≈ 1.188 n log n ، على حساب زيادة بنسبة 3% في العدد المتوقع لعمليات التبديل. ^{[ 8 ]} وهناك قاعدة محور أقوى، للمصفوفات الأكبر حجمًا، وهي اختيار العنصر التاسع ، وهو وسيط ثلاثي متكرر (Mo3)، مُعرّف على النحو التالي ^{[ 8 ].}

ninether( a ) = median(Mo3(first ⁠ 1 / 3 ⁠ of a ), Mo3(middle ⁠ 1 / 3 ⁠ of a ), Mo3(final ⁠ 1 / 3 ⁠ of a ))

يُعدّ اختيار عنصر محوري عملية معقدة أيضًا بسبب وجود تجاوز سعة الأعداد الصحيحة . فإذا كانت مؤشرات حدود المصفوفة الفرعية المراد فرزها كبيرة بما يكفي، فإنّ التعبير البسيط للمؤشر الأوسط، ( lo + hi )/2 ، سيؤدي إلى تجاوز السعة، وبالتالي الحصول على مؤشر محوري غير صالح. يمكن التغلب على هذه المشكلة باستخدام، على سبيل المثال، lo + ( hi − lo )/2 لفهرسة العنصر الأوسط، ولكن ذلك يتطلب عمليات حسابية أكثر تعقيدًا. وتظهر مشكلات مماثلة في بعض الطرق الأخرى لاختيار العنصر المحوري.

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

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

// تقوم هذه الدالة بفرز (جزء من) مصفوفة، ثم تقسمها إلى أقسام، ثم ترتب هذه الأقسام . خوارزمية الفرز السريع (A, lo, hi) هي: إذا كان lo >= 0 && lo < hi، فإن lt, gt := partition(A, lo, hi) // قيم إرجاع متعددة quicksort(A, lo, lt - 1) quicksort(A, gt + 1, hi) // تقسم الخوارزمية المصفوفة إلى ثلاثة أقسام: partition (A, lo, hi) is // قيمة المحور pivot := A[(lo + hi) / 2] // اختيار العنصر الأوسط كعنصر محور (قسمة عددية صحيحة)// فهرس أصغر، يساوي، وأكبر lt := lo eq := lo gt := hi // تكرار ومقارنة جميع العناصر مع العنصر المحوري بينما يكون eq <= gt do if A[eq] < pivot then // تبديل العناصر عند الفهرسين المتساوي والأصغر swap A[eq] with A[lt] // زيادة الفهرس الأصغر lt := lt + 1 // زيادة مؤشر التساوي المعادلة := المعادلة + 1 وإلا إذا كان A[eq] > pivot ، فقم بما يلي: // تبديل العناصر عند الفهرسين المتساوي والأكبر // تقليل الفهرس الأكبر gt := gt - 1 وإلا // إذا كانت A[eq] = pivot ، فقم بزيادة فهرس التساوي // المعادلة := المعادلة + 1 // إرجاع الفهرسين الأصغر والأكبر return lt, gt

تُعيد الخوارزمية partitionمؤشرات العنصر الأول (الأيسر) والعنصر الأخير (الأيمن) من القسم الأوسط. كل عنصر آخر في القسم يساوي العنصر المحوري، وبالتالي فهو مُرتب. ونتيجةً لذلك، لا يلزم تضمين عناصر القسم في الاستدعاءات المتكررة للدالة quicksort.

تتحقق أفضل حالة للخوارزمية عندما تكون جميع العناصر متساوية (أو مختارة من مجموعة صغيرة من k ≪ n عنصرًا). في حالة تساوي جميع العناصر، ستُجري خوارزمية الفرز السريع المُعدّلة استدعاءين متكررين فقط على المصفوفات الفرعية الفارغة، وبالتالي ستنتهي في وقت خطي (بافتراض أن الروتين partitionالفرعي لا يستغرق وقتًا أطول من الوقت الخطي).

ومن التحسينات المهمة الأخرى، التي اقترحها سيدجويك وتستخدم على نطاق واسع في الممارسة العملية، ما يلي: ^{[ 19 ] [ 20 ]}

• للتأكد من استخدام مساحة لا تتجاوز O (log n ) ، قم بالتكرار أولاً في الجانب الأصغر من القسم، ثم استخدم استدعاء الذيل للتكرار في الجانب الآخر، أو قم بتحديث المعلمات بحيث لا تشمل الجانب الأصغر الذي تم فرزه الآن، وكرر لفرز الجانب الأكبر.
• عندما يقل عدد العناصر عن حد معين (ربما عشرة عناصر)، يُنصح بالتحول إلى خوارزمية فرز غير تكرارية، مثل فرز الإدراج ، التي تُجري عمليات تبديل ومقارنات وعمليات أخرى أقل على هذه المصفوفات الصغيرة. ويختلف هذا الحد الأمثل بناءً على تفاصيل التنفيذ المحدد.
• يُعدّ هذا أحد أشكال التحسين القديمة: عندما يقلّ عدد العناصر عن العتبة k ، يتوقف البرنامج ببساطة؛ ثم بعد معالجة المصفوفة بأكملها، يُجرى عليها فرز الإدراج. يؤدي إيقاف الاستدعاء الذاتي مبكرًا إلى جعل المصفوفة مُرتبة k- مرتبة، أي أن كل عنصر يبعد k خانة على الأكثر عن موقعه النهائي المُرتب. في هذه الحالة، يستغرق فرز الإدراج زمنًا قدره O ( kn ) لإنهاء الفرز، وهو زمن خطي إذا كان k ثابتًا. ^{[ 21 ] [ 13 ] : 117} بالمقارنة مع تحسين "العديد من عمليات الفرز الصغيرة"، قد يُنفّذ هذا الإصدار عددًا أقل من التعليمات، ولكنه لا يُحسن استخدام ذاكرة التخزين المؤقت في الحواسيب الحديثة. ^{[ 22 ]}

بفضل صياغتها القائمة على فرق تسد، تُصبح خوارزمية الفرز السريع قابلةً للتوازي باستخدام توازي المهام . تتم خطوة التقسيم باستخدام خوارزمية مجموع البادئات المتوازية لحساب فهرس لكل عنصر من عناصر المصفوفة في قسمه من المصفوفة المُقسّمة. ^{[ 23 ] [ 24 ]} بافتراض مصفوفة بحجم n ، تُنجز خطوة التقسيم عملاً مقداره O( n ) في زمن قدره O (log n ) وتتطلب مساحة تخزين مؤقتة إضافية مقدارها O( n ) . بعد تقسيم المصفوفة، يُمكن فرز القسمين بشكل متكرر ومتوازٍ. بافتراض اختيار مثالي للعناصر المحورية، تُفرز خوارزمية الفرز السريع المتوازية مصفوفة بحجم n في عمل مقداره O( n log n ) في زمن قدره O(log ² n ) باستخدام مساحة تخزين إضافية مقدارها O( n ) .

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

يمكن لخوارزميات الفرز المتوازي الأخرى الأكثر تطوراً تحقيق حدود زمنية أفضل. ^{[ 25 ]} على سبيل المثال، في عام 1991، وصف ديفيد إم دبليو باورز خوارزمية فرز سريع متوازية ( وخوارزمية فرز جذرية ذات صلة ) يمكنها العمل في زمن O (log n ) على جهاز CRCW (القراءة والكتابة المتزامنة) PRAM ( آلة الوصول العشوائي المتوازية ) مع n معالجًا عن طريق إجراء التقسيم ضمنيًا. ^{[ 26 ]}

إذا كان ترتيب كل محور يقع في منتصف الخمسين بالمائة، أي بين المئين 25 والمئين 75، فإنه يقسم العناصر بحيث لا يقل ترتيبها عن 25% ولا يزيد عن 75% على كل جانب. إن اختيار محاور كهذه باستمرار سيؤدي فقط إلى تقسيم القائمة على الأكثر${\displaystyle \log _{4/3}n}$مرات قبل الوصول إلى قوائم بحجم 1، مما ينتج عنه خوارزمية O ( n log n ) .

عندما يكون المدخل عبارة عن تبديل عشوائي ، يكون للعنصر المحوري رتبة عشوائية، وبالتالي لا يُضمن وجوده ضمن النصف الأوسط. مع ذلك، عند البدء بتبديل عشوائي، يكون للعنصر المحوري في كل استدعاء تكراري رتبة عشوائية في قائمته، وبالتالي يكون ضمن النصف الأوسط لنصف الوقت تقريبًا. تخيل أننا قلبنا قطعة نقدية: ظهور الصورة يعني أن رتبة العنصر المحوري تقع ضمن النصف الأوسط، وظهور الكتابة يعني عكس ذلك. الآن تخيل أننا قلبنا القطعة النقدية مرارًا وتكرارًا حتى نحصل على k صورة. على الرغم من أن هذا قد يستغرق وقتًا طويلًا، إلا أننا نحتاج في المتوسط ​​إلى 2k قلبة فقط ، وفرصة عدم حصول القطعة النقدية على k صورة بعد 100k قلبة ضئيلة للغاية (يمكن التحقق من ذلك بدقة باستخدام حدود تشيرنوف ). وبناءً على الحجة نفسها، سينتهي التكرار في خوارزمية الفرز السريع في المتوسط ​​عند عمق استدعاء يبلغ 10 ...${\displaystyle 2\log _{4/3}n}$لكن إذا كان متوسط ​​عمق الاستدعاءات O (log n ) ، وكان كل مستوى من مستويات شجرة الاستدعاءات يعالج n عنصرًا على الأكثر، فإن إجمالي العمل المنجز في المتوسط ​​هو حاصل ضرب O ( n log n ) . لا يتعين على الخوارزمية التحقق من أن العنصر المحوري يقع في النصف الأوسط طالما أنه يقع فيه عددًا ثابتًا من المرات.

باستخدام حجج أكثر دقة، من الممكن توسيع هذا البرهان ليشمل نسخة من خوارزمية الفرز السريع حيث يتم اختيار العنصر المحوري عشوائيًا، لإظهار حد زمني يتحقق باحتمالية عالية : تحديدًا، لأي قيمة معطاة${\displaystyle a\geq 4}$، يترك${\displaystyle c=(a-4)/2}$إذن باحتمالية لا تقل عن${\displaystyle 1-{\frac {1}{n^{c}}}}$لن يتجاوز عدد المقارنات${\displaystyle 2an\log _{4/3}n}$[ ^{28 ]​}

يتمثل أحد الأساليب البديلة في إنشاء علاقة تكرارية لعامل T ( n ) ، وهو الوقت اللازم لفرز قائمة بحجم n . في الحالة الأكثر اختلالًا، تتضمن عملية فرز سريعة واحدة O ( n ) من العمل بالإضافة إلى عمليتي استدعاء متكررتين على قوائم بحجم 0 و n -1 ، لذا فإن العلاقة التكرارية هي

${\displaystyle T(n)=O(n)+T(0)+T(n-1)=O(n)+T(n-1).}$

هذه هي نفس العلاقة كما هو الحال بالنسبة لفرز الإدراج وفرز الاختيار ، ويتم حلها إلى أسوأ حالة T ( n ) = O ( n ² ) .

في الحالة الأكثر توازناً، تتضمن عملية استدعاء واحدة لخوارزمية الفرز السريع O ( n ) من العمليات بالإضافة إلى استدعاءين متكررين على قوائم بحجم n /2 ، لذا فإن علاقة التكرار هي

${\displaystyle T(n)=O(n)+2T\left({\frac {n}{2}}\right).}$

تخبرنا النظرية الرئيسية للتكرارات التي تعتمد على فرق تسد أن T ( n ) = O ( n log n ) .

فيما يلي ملخص لإثبات رسمي لتعقيد الوقت المتوقع O ( n log n ) . نفترض عدم وجود عناصر مكررة، إذ يمكن معالجتها مسبقًا وبعديًا بزمن خطي، أو اعتبارها حالات أسهل من الحالة المدروسة. عندما يكون المدخل عبارة عن تبديل عشوائي، تكون رتبة العنصر المحوري عشوائية بشكل منتظم من 0 إلى n -1 . عندئذٍ، يكون حجم الأجزاء الناتجة من التقسيم i و n - i -1 ، و i عشوائية بشكل منتظم من 0 إلى n -1 . لذا، بحساب المتوسط ​​لجميع التقسيمات الممكنة، مع ملاحظة أن عدد المقارنات للتقسيم هو n -1 ، يمكن تقدير متوسط ​​عدد المقارنات لجميع تباديل تسلسل المدخل بدقة عن طريق حل العلاقة التكرارية التالية:

${\displaystyle C(n)=n-1+{\frac {1}{n}}\sum _{i=0}^{n-1}(C(i)+C(n-i-1))=n-1+{\frac {2}{n}}\sum _{i=0}^{n-1}C(i)}$

${\displaystyle nC(n)=n(n-1)+2\sum _{i=0}^{n-1}C(i)}$

${\displaystyle nC(n)-(n-1)C(n-1)=n(n-1)-(n-1)(n-2)+2C(n-1)}$

${\displaystyle nC(n)=(n+1)C(n-1)+2n-2}$

${\displaystyle {\begin{aligned}{\frac {C(n)}{n+1}}&={\frac {C(n-1)}{n}}+{\frac {2}{n+1}}-{\frac {2}{n(n+1)}}\leq {\frac {C(n-1)}{n}}+{\frac {2}{n+1}}\\&={\frac {C(n-2)}{n-1}}+{\frac {2}{n}}-{\frac {2}{(n-1)n}}+{\frac {2}{n+1}}\leq {\frac {C(n-2)}{n-1}}+{\frac {2}{n}}+{\frac {2}{n+1}}\\&\ \ \vdots \\&={\frac {C(1)}{2}}+\sum _{i=2}^{n}{\frac {2}{i+1}}\leq 2\sum _{i=1}^{n-1}{\frac {1}{i}}\approx 2\int _{1}^{n}{\frac {1}{x}}\mathrm {d} x=2\ln n\end{aligned}}}$

حل التكرار يعطي C ( n ) = 2 n ln n ≈ 1.39 n log ₂ n .

هذا يعني أن أداء خوارزمية الفرز السريع، في المتوسط، أسوأ بنسبة 39% فقط من أفضل حالاتها. وبهذا المعنى، فهي أقرب إلى أفضل الحالات منها إلى أسوأها. لا يمكن لخوارزمية الفرز المقارن استخدام أقل من log₂ ( n !) مقارنة في المتوسط ​​لفرز _n عنصرًا (كما هو موضح في مقالة الفرز المقارن ) _، وفي حالة n الكبيرة ، يُعطي تقريب ستيرلينغ log₂ ( n !) ≈ n (log₂n _- log₂e ₎ ، لذا فإن أداء الفرز السريع ليس أسوأ بكثير من الفرز المقارن المثالي. يُعد متوسط ​​وقت التشغيل السريع هذا سببًا آخر لتفوق الفرز السريع عمليًا على خوارزميات الفرز الأخرى.

تُقابل كل عملية تنفيذ لخوارزمية الفرز السريع شجرة بحث ثنائية (BST) كما يلي : العقدة المحورية الأولية هي العقدة الجذرية؛ وعقدة النصف الأيسر هي جذر الشجرة الفرعية اليسرى، وعقدة النصف الأيمن هي جذر الشجرة الفرعية اليمنى، وهكذا. عدد المقارنات في عملية تنفيذ الفرز السريع يساوي عدد المقارنات أثناء بناء شجرة البحث الثنائية من خلال سلسلة من عمليات الإدخال. لذا، فإن متوسط ​​عدد المقارنات في الفرز السريع العشوائي يساوي متوسط ​​تكلفة بناء شجرة البحث الثنائية عند إدخال القيم.${\displaystyle (x_{1},x_{2},\ldots ,x_{n})}$قم بتشكيل تبديل عشوائي.

لنفترض وجود شجرة بحث ثنائية تم إنشاؤها عن طريق إدخال تسلسل${\displaystyle (x_{1},x_{2},\ldots ,x_{n})}$من القيم التي تشكل تبديلاً عشوائياً. لنفترض أن C ترمز إلى تكلفة إنشاء شجرة البحث الثنائية. لدينا${\displaystyle C=\sum _{i}\sum _{j<i}c_{i,j}}$، أين${\displaystyle c_{i,j}}$هو متغير عشوائي ثنائي يعبر عما إذا كان أثناء إدخال${\displaystyle x_{i}}$كانت هناك مقارنة بـ${\displaystyle x_{j}}$.

بحسب خاصية الخطية للتوقع ، فإن القيمة المتوقعة${\displaystyle \operatorname {E} [C]}$من C هو${\displaystyle \operatorname {E} [C]=\sum _{i}\sum _{j<i}\Pr(c_{i,j})}$.

ثبّت i و j < i . القيم${\displaystyle {x_{1},x_{2},\ldots ,x_{j}}}$بعد فرزها، حدد فترات j + 1. الملاحظة الهيكلية الأساسية هي أن${\displaystyle x_{i}}$مقارنة بـ${\displaystyle x_{j}}$في الخوارزمية إذا وفقط إذا${\displaystyle x_{i}}$يقع ضمن إحدى الفترتين المجاورتين لـ${\displaystyle x_{j}}$.

لاحظ ذلك منذ${\displaystyle (x_{1},x_{2},\ldots ,x_{n})}$هو تبديل عشوائي،${\displaystyle (x_{1},x_{2},\ldots ,x_{j},x_{i})}$وهي أيضًا تبديل عشوائي، لذا فإن احتمال أن${\displaystyle x_{i}}$يقع بجوار${\displaystyle x_{j}}$هو بالضبط${\displaystyle {\frac {2}{j+1}}}$.

مبسطة كعملية حسابية مختصرة:

${\displaystyle \operatorname {E} [C]=\sum _{i}\sum _{j<i}{\frac {2}{j+1}}=O\left(\sum _{i}\log i\right)=O(n\log n).}$

بدلاً من تقسيم البيانات إلى مصفوفتين فرعيتين باستخدام محور واحد، يقوم فرز البيانات السريع متعدد المحاور (أو فرز البيانات السريع المتعدد ^{[ 22 ]} ) بتقسيم المدخلات إلى عدد s من المصفوفات الفرعية باستخدام s − 1 محور. وبينما درس سيدجويك وآخرون حالة المحورين ( s = 3 ) في منتصف سبعينيات القرن الماضي، لم تكن الخوارزميات الناتجة أسرع عمليًا من فرز البيانات السريع "الكلاسيكي". ^{[ 34 ]} وفي تقييم أُجري عام 1999 لفرز البيانات السريع المتعدد ذي عدد متغير من المحاور، والمُحسَّن للاستخدام الأمثل لذاكرة التخزين المؤقت للمعالج، وُجد أنه يزيد عدد التعليمات بنحو 20%، لكن نتائج المحاكاة أشارت إلى أنه سيكون أكثر كفاءة مع المدخلات الكبيرة جدًا. ^{[ 22 ]} تبين أن نسخة من خوارزمية الفرز السريع ثنائية المحور، التي طورها ياروسلافسكي عام 2009 ^{[ 35 ] ، سريعة بما يكفي [ 36 ]} لتبرير تطبيقها في جافا 7 ، كخوارزمية قياسية لفرز مصفوفات العناصر الأولية ( يتم فرز مصفوفات الكائنات باستخدام خوارزمية Timsort ). ^{[ 37 ]} وقد تبين لاحقًا أن تحسن أداء هذه الخوارزمية مرتبط في الغالب بأداء الذاكرة المؤقتة، ^{[ 38 ]} وتشير النتائج التجريبية إلى أن النسخة ثلاثية المحور قد يكون أداؤها أفضل على الأجهزة الحديثة. ^{[ 39 ] [ 40 ]}

بالنسبة لملفات القرص، يُمكن استخدام فرز خارجي قائم على التقسيم، على غرار الفرز السريع. وهو أبطأ من فرز الدمج الخارجي، ولكنه لا يتطلب مساحة إضافية على القرص. يتم استخدام 4 مخازن مؤقتة، اثنان للإدخال واثنان للإخراج.${\displaystyle N=}$عدد السجلات في الملف،${\displaystyle B=}$عدد السجلات لكل مخزن مؤقت، و${\displaystyle M=N/B=}$عدد أجزاء المخزن المؤقت في الملف. تُقرأ البيانات (وتُكتب) من طرفي الملف باتجاه الداخل. ليكن${\displaystyle X}$تمثل هذه المقاطع الأجزاء التي تبدأ من بداية الملف، و${\displaystyle Y}$تمثل هذه المقاطع أجزاءً تبدأ من نهاية الملف. تُقرأ البيانات في${\displaystyle X}$و${\displaystyle Y}$قراءة المخازن المؤقتة. يتم اختيار سجل محوري والسجلات الموجودة فيه${\displaystyle X}$و${\displaystyle Y}$يتم نسخ المخازن المؤقتة الأخرى غير سجل المحور إلى${\displaystyle X}$اكتب البيانات المخزنة مؤقتًا بترتيب تصاعدي و${\displaystyle Y}$يتم كتابة البيانات المخزنة مؤقتًا بترتيب تنازلي بناءً على المقارنة مع سجل المحور. بمجرد حدوث أي مما يلي${\displaystyle X}$أو${\displaystyle Y}$يتم ملء المخزن المؤقت، ثم تتم كتابته في الملف، ثم التالي${\displaystyle X}$أو${\displaystyle Y}$تُقرأ البيانات من الملف. وتستمر العملية حتى تُقرأ جميع الأجزاء ويبقى مخزن كتابة واحد. إذا كان هذا المخزن عبارة عن${\displaystyle X}$يتم إلحاق سجل المحور بذاكرة التخزين المؤقت للكتابة، و${\displaystyle X}$يتم كتابة البيانات في المخزن المؤقت. إذا كان هذا المخزن المؤقت عبارة عن${\displaystyle Y}$في مخزن الكتابة، يتم إلحاق سجل المحور بـ${\displaystyle Y}$المخزن المؤقت و${\displaystyle Y}$تمت كتابة المخزن المؤقت. يُمثل هذا خطوة تقسيم واحدة للملف، ويتكون الملف الآن من ملفين فرعيين. يتم دفع/سحب موضعَي البداية والنهاية لكل ملف فرعي إلى مكدس مستقل أو المكدس الرئيسي عبر التكرار. لتقييد مساحة المكدس إلى${\displaystyle O(\log _{2}(n))}$في حالة المعالجة المتكررة، تتم معالجة الملف الفرعي الأصغر أولاً. بالنسبة للمكدس المستقل، تُضاف معلمات الملف الفرعي الأكبر إلى المكدس، ثم تُكرر العملية على الملف الفرعي الأصغر. أما في حالة المعالجة المتكررة، فتُكرر العملية على الملف الفرعي الأصغر أولاً، ثم تُكرر لمعالجة الملف الفرعي الأكبر. بمجرد أن يصبح حجم الملف الفرعي أقل من أو يساوي 4 بايتات من السجلات، يُرتب الملف الفرعي في مكانه باستخدام خوارزمية الفرز السريع ويُكتب. يصبح هذا الملف الفرعي الآن مُرتبًا وموجودًا في مكانه في الملف. تستمر هذه العملية حتى يتم ترتيب جميع الملفات الفرعية وإضافتها إلى مكانها. يبلغ متوسط ​​عدد مرات المرور على الملف حوالي${\displaystyle {\frac {1+\ln(N+1)}{(4B)}}}$لكن أسوأ سيناريو هو${\displaystyle N}$النجاحات (ما يعادل${\displaystyle O(n^{2})}$(للحالات الأسوأ، الفرز الداخلي). ^{[ 41 ]}

تجمع هذه الخوارزمية بين فرز الجذر والفرز السريع. اختر عنصرًا من المصفوفة (العنصر المحوري) وحدد الحرف الأول (المفتاح) من السلسلة (مفتاح متعدد). قسّم العناصر المتبقية إلى ثلاث مجموعات: تلك التي يكون الحرف المقابل لها أصغر من، أو يساوي، أو أكبر من حرف العنصر المحوري. رتّب مجموعتي "أصغر من" و"أكبر من" بشكل متكرر بناءً على الحرف نفسه. رتّب مجموعة "يساوي" بشكل متكرر بناءً على الحرف التالي (المفتاح). بما أننا نستخدم بايتات أو كلمات بطول W بت للفرز، فإن أفضل حالة هي O ( KN ) وأسوأ حالة هي O (2KN ⁾ أو على الأقل O ( N² ) كما هو الحال في الفرز السريع القياسي، وذلك للمفاتيح الفريدة N < 2K ^، حيث K ثابت ضمني في جميع خوارزميات فرز المقارنة القياسية ، بما في ذلك الفرز السريع. هذا نوع من الفرز السريع ثلاثي الاتجاهات ^، حيث يمثل القسم الأوسط مصفوفة فرعية مرتبة (بشكل بديهي) من العناصر التي تساوي العنصر المحوري تمامًا .

طُوِّرت هذه الخوارزمية أيضًا بواسطة باورز كخوارزمية PRAM متوازية من رتبة O ( K ) . وهي بدورها مزيج من فرز الجذر والفرز السريع، ولكن قرار تقسيم المفتاح إلى يمين أو يسار في الفرز السريع يعتمد على البتات المتتالية للمفتاح، وبالتالي يكون زمنها O ( KN ) لمفاتيح N ذات K بت. تفترض جميع خوارزميات فرز المقارنة ضمنيًا نموذجًا ثنائيًا متقاطعًا حيث K في Θ (log N ) ، فإذا كانت K أصغر، يمكننا الفرز في زمن O ( N ) باستخدام جدول تجزئة أو فرز الأعداد الصحيحة . أما إذا كانت K أكبر بكثير من log N ، ولكن العناصر فريدة ضمن O (log N ) بت، فلن يتم فحص البتات المتبقية بواسطة الفرز السريع أو فرز الجذر السريع. وإلا، فإن جميع خوارزميات فرز المقارنة ستتحمل نفس العبء الإضافي المتمثل في البحث في O ( K ) ^من البتات غير المفيدة نسبيًا، لكن فرز الجذر السريع سيتجنب أسوأ حالات O ( N² ) لسلوكيات الفرز السريع القياسي وفرز الجذر السريع، وسيكون أسرع حتى في أفضل حالات خوارزميات المقارنة هذه في ظل هذه الشروط: uniqueprefix( K ) ≫ log N. انظر Powers ^{[ 42 ]} لمزيد من المناقشة حول الأعباء الإضافية الخفية في فرز المقارنة، وفرز الجذر، والفرز المتوازي.

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

The BlockQuicksort technique is incorporated into LLVM's C++ STL implementation, libcxx, providing a 50% improvement on random integer sequences. Pattern-defeating quicksort (pdqsort), a version of introsort, also incorporates this technique.^[33]

Several variants of quicksort exist that separate the k smallest or largest elements from the rest of the input.