🃏 الترتيب: ثمن السرعة

البحث الثنائي اشترط قائمة مرتبة — فمن يقوم بالترتيب؟ الترتيب رسمٌ تدفعه مرة واحدة لتصبح كل عمليات البحث اللاحقة شبه مجانية. وأبسط وصفة هي الترتيب الفقاعي: امشِ في القائمة، قارن كل جارين، وبدّلهما إن كانا معكوسين. كرر حتى تمر جولة كاملة بلا تبديل. القيم الكبيرة «تطفو» نحو النهاية كفقاعات الهواء في الماء.

وهنا اللسعة: n × n تعني أن ترتيب مليون عنصر فقاعياً ≈ تريليون مقارنة. المكتبات الحقيقية تستخدم وصفات أذكى (دالة sorted() المدمجة في بايثون تشغّل وصفة اسمها Timsort) تنتهي في n × log(n) — مليون عنصر في نحو 20 مليون خطوة، لا تريليون.