تيمسورت

📅 آخر تحديث: ٢٦ يوليو ٢٠٢٦
✍️ نُشر في: ٢٦ يوليو ٢٠٢٦
📷 يحتوي على 23 صور
الموسوعة الحرة

Timsort هي خوارزمية فرز هجينة ومستقرة ، مشتقة من فرز الدمج وفرز الإدراج ، ومصممة لتحقيق أداء ممتاز مع أنواع عديدة من البيانات الواقعية. قام تيم بيترز بتطويرها عام 2002 لاستخدامها في لغة البرمجة بايثون . تعتمد الخوارزمية على إيجاد سلاسل فرعية من البيانات المرتبة مسبقًا (المجموعات) واستخدامها لفرز البيانات المتبقية بكفاءة أكبر. يتم ذلك عن طريق دمج المجموعات الفرعية حتى يتم استيفاء معايير محددة. كانت Timsort خوارزمية الفرز القياسية في بايثون من الإصدار 2.3 حتى تم استبدالها في الإصدار 3.11 بخوارزمية Powersort ، وهي خوارزمية مشتقة ذات سياسة دمج أكثر قوة. [ 5 ] تُستخدم Timsort أيضًا لفرز المصفوفات من الأنواع غير الأولية في Java SE 7 ، [ 6 ] وعلى منصة Android ، [ 7 ] وفي GNU Octave ، [ 8 ] وعلى V8 ، [ 9 ] وفي Swift . [ 10 ] استخدمت لغة Rust نسخة مخصصة من Timsort حتى مايو 2024. [ 11 ]

تستند تقنية التسارع إلى ورقة كارلسون وليفكوبولوس وأو. بيترسون البحثية لعام 1990 بعنوان "الدمج شبه الخطي وفرز الدمج الطبيعي" وورقة بيتر ماكلروي البحثية لعام 1993 بعنوان "الفرز التفاؤلي وتعقيد نظرية المعلومات". [ 12 ]

عملية

صُممت خوارزمية Timsort للاستفادة من سلاسل العناصر المتتالية المرتبة الموجودة في معظم بيانات العالم الحقيقي، وهي ما يُعرف بالسلاسل الطبيعية . تُكرر هذه الخوارزمية عملية جمع العناصر في سلاسل، ثم تضع هذه السلاسل في مكدس. عندما تتطابق السلاسل الموجودة في أعلى المكدس مع معيار الدمج ، يتم دمجها. يستمر هذا حتى يتم استعراض جميع البيانات؛ عندئذٍ، يتم دمج جميع السلاسل اثنتين اثنتين، وتبقى سلسلة واحدة مرتبة فقط. تكمن ميزة دمج السلاسل المرتبة، بدلاً من دمج القوائم الفرعية ذات الحجم الثابت (كما هو الحال في خوارزمية mergesort التقليدية)، في تقليل العدد الإجمالي للمقارنات اللازمة لفرز القائمة بأكملها.

لكل عملية تشغيل حد أدنى للحجم، يعتمد على حجم المدخلات ويُحدد في بداية الخوارزمية. إذا كانت عملية التشغيل أصغر من هذا الحد الأدنى، يُستخدم فرز الإدراج لإضافة المزيد من العناصر إلى عملية التشغيل حتى الوصول إلى الحد الأدنى للحجم.

معايير الدمج

تُضاف التسلسلات إلى مكدس . إذا كان | Z | ≤ | Y | + | X | ، يتم دمج X و Y وإعادتهما إلى المكدس. بهذه الطريقة، يستمر الدمج حتى تحقق جميع التسلسلات الشرطين التاليين : 1. | Z | > | Y | + | X | و 2. | Y | > | X | .

Timsort هي خوارزمية فرز مستقرة (يتم الاحتفاظ بترتيب العناصر التي لها نفس المفتاح) وتسعى جاهدة لإجراء عمليات دمج متوازنة (وبالتالي فإن عملية الدمج تدمج سلاسل ذات أحجام متشابهة).

لتحقيق استقرار الترتيب، يتم دمج التسلسلات المتتالية فقط. قد يوجد بين تسلسلين غير متتاليين عنصرٌ يحمل نفس المفتاح. دمج هذين التسلسلين سيغير ترتيب المفاتيح المتساوية. مثال على هذه الحالة (التسلسلات المرتبة هي []): [1 2 2] 1 4 2 [0 1 2]

سعياً وراء عمليات الدمج المتوازنة، يأخذ Timsort في الاعتبار ثلاث عمليات تشغيل على قمة المكدس، X و Y و Z ، ويحافظ على الثوابت:

  1. | Z | > | Y | + | X |
  2. | Y | > | X | [ 13 ]

إذا انتُهكت أيٌّ من هذه الثوابت، يُدمج Y مع أصغر قيمة بين X أو Z ، ثم تُعاد دراسة الثوابت. وبمجرد استيفاء الشروط، يمكن البدء بالبحث عن سلسلة جديدة في البيانات. [ 14 ] تحافظ هذه الثوابت على توازن عمليات الدمج تقريبًا، مع مراعاة التوازن بين تأخير الدمج لتحقيق التوازن، واستغلال ظهور السلاسل الجديدة في ذاكرة التخزين المؤقت ، وتبسيط قرارات الدمج نسبيًا.

مساحة الدمج العلوية

لدمج العناصر، يقوم برنامج Timsort بنسخ عناصر المصفوفة الأصغر (X في هذا المثال التوضيحي) إلى ذاكرة مؤقتة، ثم يقوم بفرز العناصر وملءها بالترتيب النهائي في المساحة المدمجة لـ X و Y.

إنّ تطبيق فرز الدمج الأصلي ليس مُدمجًا في مكانه، ويستهلك مساحة إضافية تُقدّر بحجم البيانات (N). توجد تطبيقات لفرز الدمج مُدمجة في مكانها، ولكنها تستهلك وقتًا طويلًا. ولتحقيق حل وسط، يُجري Timsort فرز دمج باستهلاك زمني ومساحة أقل من N.

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

مثال: يجب دمج سلسلتين [1، 2، 3، 6، 10] و[4، 5، 7، 9، 12، 14، 17]. لاحظ أن كلتا السلسلتين مُرتبتان بشكل منفصل. أصغر عنصر في السلسلة الثانية هو 4، ويجب إضافته في الموضع الرابع من السلسلة الأولى للحفاظ على ترتيبها (بافتراض أن الموضع الأول في السلسلة هو 1). أكبر عنصر في السلسلة الأولى هو 10، ويجب إضافته في الموضع الخامس من السلسلة الثانية للحفاظ على ترتيبها. بالتالي، فإن السلسلتين [1، 2، 3] و[12، 14، 17] هما في موضعيهما النهائيين، والسلسلتان اللتان تتطلبان تحريك العناصر هما [6، 10] و[4، 5، 7، 9]. بناءً على هذه المعلومات، نحتاج فقط إلى تخصيص مخزن مؤقت بحجم 2 بدلاً من 4.

اتجاه الدمج

يمكن إجراء عملية الدمج في كلا الاتجاهين: من اليسار إلى اليمين، كما هو الحال في فرز الدمج التقليدي، أو من اليمين إلى اليسار.

وضع التسارع أثناء الدمج

تتم مقارنة العناصر (المشار إليها بالسهم الأزرق) ويتم نقل العنصر الأصغر إلى موضعه النهائي (المشار إليه بالسهم الأحمر).

عند دمج مجموعتي البيانات R1 وR2، يتم الاحتفاظ بعدد العناصر المتتالية المختارة من كل مجموعة. عندما يصل هذا العدد إلى الحد الأدنى لعتبة التسارع ( min_gallop )، يعتبر Timsort أنه من المحتمل اختيار العديد من العناصر المتتالية من تلك المجموعة، فينتقل إلى وضع التسارع. لنفترض أن R1 هو المسؤول عن بدء هذا الوضع. في هذا الوضع، تُجري الخوارزمية بحثًا على مرحلتين للعثور على الموضع في مجموعة البيانات R1 حيث سيتم إدراج العنصر x التالي من مجموعة البيانات R2. في المرحلة الأولى، تُجري بحثًا أُسّيًا ، يُعرف أيضًا بالبحث المتسارع، حتى يتم العثور على قيمة k بحيث يكون R1[ 2k- 1-1] < x <= R1[ 2k -1]، أي منطقة عدم يقين تضم 2k - 1-1 عنصرًا متتاليًا من R1. في المرحلة الثانية، تُجري بحثًا ثنائيًا مباشرًا في هذه المنطقة للعثور على الموقع الدقيق لـ x في R1 . الوضع المتسارع هو محاولة لتكييف خوارزمية الدمج مع نمط الفواصل الزمنية بين العناصر في التسلسلات.

جميع العناصر الحمراء أصغر من العناصر الزرقاء (هنا، 21). وبالتالي يمكن نقلها كمجموعة إلى المصفوفة النهائية.

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

الجري الهابط

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

الحد الأدنى لحجم التشغيل

تبحث خوارزمية Timsort عن التسلسلات المرتبة ذات الحجم الأدنى، أو ما يُعرف بـ minruns، لتنفيذ عملية الفرز.

لأن عملية الدمج تكون أكثر كفاءة عندما يكون عدد مرات التشغيل مساوياً أو أقل بقليل من قوة العدد اثنين، وتكون أقل كفاءة بشكل ملحوظ عندما يكون عدد مرات التشغيل أكبر بقليل من قوة العدد اثنين، فإن خوارزمية Timsort تختار minrun لمحاولة ضمان الشرط الأول. [ 13 ]

يُختار الحد الأدنى للتشغيل (minrun) من النطاق 32 إلى 64 شاملًا، بحيث يكون حجم البيانات، مقسومًا على الحد الأدنى للتشغيل ، مساويًا أو أقل بقليل من قوة العدد 2. تأخذ الخوارزمية النهائية البتات الستة الأكثر أهمية من حجم المصفوفة، وتضيف واحدًا إذا كانت أي من البتات المتبقية مُفعّلة، وتستخدم هذه النتيجة كقيمة للحد الأدنى للتشغيل . تعمل هذه الخوارزمية مع جميع المصفوفات، بما في ذلك تلك التي يقل حجمها عن 64؛ أما بالنسبة للمصفوفات التي يبلغ حجمها 63 أو أقل، فإن هذا يجعل قيمة الحد الأدنى للتشغيل مساوية لحجم المصفوفة، ويتحول فرز Timsort إلى فرز إدراج. [ 13 ]

الخوارزمية

كما هو موضح أعلاه، تتكون خوارزمية Timsort من عدة أجزاء، يصعب وصفها هنا باستخدام الشفرة الزائفة. ننصح القراء المهتمين بشدة بالاطلاع على أحد الإصدارات التالية (مع إصلاح حجم المكدس لعام 2015):

  • تم تنفيذه بلغة جافا، من إصدار OpenJDK 11. 940 سطرًا من التعليمات البرمجية، منها 403 أسطر ليست فارغة ولا مجرد تعليقات. [ 16 ]
  • تم تنفيذ البرنامج بلغة C، باستخدام CPython الإصدار 3.4.10. يبدأ كود Timsort من السطر 965 وينتهي عند السطر 2084، بإجمالي 1120 سطرًا، منها 732 سطرًا ليست فارغة ولا تعليقات فقط. [ 17 ]
  • تم تنفيذ البرنامج بلغة بايثون، من تحديث PyPy رقم "7fce1e5"، وهو آخر تحديث قبل دمج سياسة "Powersort". يتكون البرنامج من 636 سطرًا من التعليمات البرمجية، منها 486 سطرًا ليست فارغة ولا مجرد تعليقات. [ 18 ]

تحليل

في أسوأ الأحوال ، يتولى Timsortيا(نسجل⁡ن){\displaystyle O(n\log n)}مقارنات لفرز مجموعة منن{\displaystyle n}العناصر. في أفضل الأحوال، والتي تحدث عندما تكون المدخلات مرتبة بالفعل، فإنها تعمل في وقت خطي، مما يعني أنها خوارزمية فرز تكيفية . [ 3 ]

بالنسبة للمدخل الذي يحتوير{\displaystyle r}مدة تشغيل سلاسل العناصر المصنفة هييا(نسجل⁡ر){\displaystyle O(n\log r)}وبقوة أكبر، الوقت هويا(ن+نح){\displaystyle O(n+n\mathrm {H} )}، حيث إنتروبيا طول التشغيلح{\displaystyle \mathrm {H} }من مدخلات يكون فيهاأنا{\displaystyle i}حجم الجرينأنا{\displaystyle n_{i}}يُعرَّف بأنه [ 2 ]ح=-∑أنا=1رنأنانسجل2⁡نأنان.{\displaystyle \mathrm {H} =-\sum _{i=1}^{r}{\frac {n_{i}}{n}}\log _{2}{\frac {n_{i}}{n}}.} عندما تتساوى جميع أحجام التشغيل، فإن إنتروبيا طول التشغيلسجل2⁡ر{\displaystyle \log _{2}r}، قيمتها القصوى لأي رقم معينر{\displaystyle r}عدد مرات التشغيل، ولكن قد يكون أقل عندما تكون أحجام مرات التشغيل غير متساوية. صيغة وقت التشغيل هي كالتالي:ن+نح{\displaystyle n+n\mathrm {H} }بدلاً من ذلك ببساطةنح{\displaystyle n\mathrm {H} }، وذلك لمراعاة احتمال أن تكون قيمة الإنتروبيا أقل من واحد. [ 2 ]

السلوك المذكور أعلاه فيما يتعلق بإنتروبيا طول التشغيلح{\displaystyle \mathrm {H} }يُستمد هذا بشكل كامل من معايير دمج Timsort، حيث أن هذا هو الجزء المسؤول عن اكتشاف الأجزاء المصنفة مسبقًا. يستغل روتين "التسارع" خاصية جديدة يمكن وصفها بأنها إنتروبيا التشغيل المزدوجح*{\displaystyle \mathrm {H} ^{*}}[ 19 ]​ح*=-∑أنا=1sنأنانسجل2⁡نأنان.{\displaystyle \mathrm {H} ^{*}=-\sum _{i=1}^{s}{\frac {n_{i}}{n}}\log _{2}{\frac {n_{i}}{n}}.} أينs{\displaystyle s}عدد مرات انقطاع "الركض" بواسطة وs≤ر{\displaystyle s\leq r}يمكن إثبات أن برنامج TimSort يستغرق ما يصل إلىيا(ن+نح){\displaystyle O(n+n\mathrm {H} )}يتحرك العنصر ويا(ن+نح*){\displaystyle O(n+n\mathrm {H} ^{*})}مقارنات القيمة. [ 19 ]

التبني والتأثير

تأثير

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

  • تتمتع خوارزميات Peeksort و Powersort وAdaptive ShiversSort وα-Mergesort بنفس الخاصية فيما يتعلق بـح*{\displaystyle \mathrm {H} ^{*}}[ 19 ]​
  • لا تمتلك خوارزميات NaturalMergeSort و ShiversSort و α-StackSort الخاصية فيما يتعلق بـح*{\displaystyle \mathrm {H} ^{*}}لأنها لا تستطيع دمج سوى العنصرين العلويين من مكدسها. [ 19 ]
  • تستغرق خوارزميات NaturalMergeSort و ShiversSort و PowerSort ما يصل إلىنسجل2⁡ن+يا(ن){\displaystyle n\log _{2}n+O(n)}المقارنات. [ 19 ]

وتشمل التأثيرات الأخرى ما يلي:

التحقق الرسمي

في عام 2015، اكتشف باحثون هولنديون وألمان في مشروع ENVISAGE التابع للبرنامج الإطاري السابع للاتحاد الأوروبي خطأً في التطبيق القياسي لخوارزمية Timsort. [ 21 ] وقد تم إصلاح هذا الخطأ في عام 2015 في لغات البرمجة Python وJava وAndroid.

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

مع ذلك، يشترط الضمان تطبيق الثوابت على كل مجموعة من ثلاث عمليات تشغيل متتالية، لكن التطبيق لم يتحقق من ذلك إلا لأول ثلاث عمليات تشغيل. [ 21 ] باستخدام أداة KeY للتحقق الرسمي من برمجيات جافا، وجد الباحثون أن هذا التحقق غير كافٍ، وتمكنوا من تحديد أطوال عمليات التشغيل (والمدخلات التي ولّدت هذه الأطوال) التي تؤدي إلى انتهاك الثوابت في طبقات أعمق من المكدس بعد دمج الطبقة العليا منه. [ 22 ]

نتيجةً لذلك، بالنسبة لبعض المدخلات، لا يكون الحجم المخصص كافيًا لاستيعاب جميع عمليات التشغيل غير المدمجة. في لغة جافا، يُولّد هذا استثناءً خارج نطاق المصفوفة لتلك المدخلات. أصغر مدخل يُسبب هذا الاستثناء في جافا وأندرويد الإصدار 7 هو بحجم67 108 864 (2 26 ). (كانت الإصدارات القديمة من نظام أندرويد تُفعّل هذا الاستثناء بالفعل لبعض المدخلات ذات الحجم65536 ( 216 ) )

تم تصحيح تطبيق جافا بزيادة حجم المكدس المُخصص مسبقًا بناءً على تحليل مُحدَّث لأسوأ الحالات. كما أوضحت المقالة، باستخدام أساليب رسمية، كيفية إثبات الثابت المقصود من خلال التحقق من أن عمليات التشغيل الأربع العليا في المكدس تُحقق القاعدتين المذكورتين أعلاه. وقد اعتمدت بايثون هذا النهج في البداية [ 23 ] حتى تحولت إلى خوارزمية Powersort في عام 2022 مع إصدار بايثون 3.11. [ 5 ]

مراجع

  1. ↑ بيترز، تيم (20 يوليو 2002). " [ Python-Dev ] الفرز" . قائمة بريدية لمطوري بايثون . تم الاطلاع عليه في 24 فبراير 2011. [Timsort] له أيضًا جوانب جيدة: فهو مستقر (تحتفظ العناصر المتساوية في الترتيب بترتيبها النسبي، على سبيل المثال، إذا قمت بالفرز أولاً حسب الرمز البريدي، ثم مرة ثانية حسب الاسم، فسيظل الأشخاص الذين يحملون نفس الاسم يظهرون بترتيب تصاعدي للرمز البريدي؛ وهذا مهم في التطبيقات التي، على سبيل المثال، تُحسّن نتائج الاستعلامات بناءً على مدخلات المستخدم). ... ليس لديه حالات سيئة (O(N log N) هي أسوأ حالة؛ N−1 مقارنة هي أفضل حالة).
  2. 1 2 3 أوجيه، نيكولاس؛ جوجي، فنسنت؛ نيكود، سيريل؛ بيفوتو ، كارين (2018). “في أسوأ الأحوال تعقيد TimSort”. وفي عازار يوسي؛ باست, هانا ; هيرمان، جريزيجورز (محرران). الندوة الأوروبية السنوية السادسة والعشرون حول الخوارزميات، وكالة الفضاء الأوروبية 2018، 20-22 أغسطس 2018، هلسنكي، فنلندا . LIPics. المجلد. 112. شلوس داغستوهل – مركز لايبنتز للمعلوماتية. ص 4: 1-4: 13. أرخايف : 1805.08612 . دوى : 10.4230/LIPIcs.ESA.2018.4 .  
  3. 1 2 تشاندرا مولي، بادريش؛ غولدشتاين، جوناثان (2014). "الصبر فضيلة: إعادة النظر في دمج وفرز البيانات على المعالجات الحديثة" . في: دايرسون، كورتيس إي؛ لي، فيفي؛ أوزسو، إم. تامر (محررون). المؤتمر الدولي لإدارة البيانات، SIGMOD 2014، سنو بيرد، يوتا، الولايات المتحدة الأمريكية، 22-27 يونيو 2014. رابطة آلات الحوسبة. الصفحات 731-742 . doi : 10.1145/2588555.2593662 . 
  4. ↑ مونرو، ج. إيان ؛ وايلد، سيباستيان (2018). "خوارزميات الفرز الدمج شبه المثلى: طرق فرز سريعة وعملية تتكيف على النحو الأمثل مع عمليات التشغيل الحالية". في: آزار، يوسي؛ باست، هانا ؛ هيرمان، غريغورز (محررون). الندوة الأوروبية السنوية السادسة والعشرون حول الخوارزميات، ESA 2018، 20-22 أغسطس 2018، هلسنكي، فنلندا . LIPIcs. المجلد 112. شلوس داغشتول - مركز لايبنيز للمعلوماتية. الصفحات 63:1-63:16. doi : 10.4230/LIPICS.ESA.2018.63 .  
  5. 1 2 جيمس، مايك. "بايثون تستخدم الآن خوارزمية فرز القوى" . مبرمج . تم الاسترجاع في 21 يونيو 2024 .
  6. ↑ " [ #JDK-6804124 ] (coll) استبدل " modified mergesort " في java.util.Arrays.sort بـ timsort" . نظام أخطاء JDK . تم الاطلاع عليه بتاريخ 11 يونيو 2014 .
  7. ↑ "الفئة: java.util.TimSort<T>" . وثائق أندرويد جينجربريد . مؤرشفة من الأصل في 16 يوليو 2015. تم الاطلاع عليها في 24 فبراير 2011 .
  8. ↑ "liboctave/util/oct-sort.cc" . مستودع ميركوريال لشفرة مصدر أوكتاف . الأسطر 23-25 ​​من كتلة التعليقات الأولية . تم استرجاعها في 18 فبراير 2013. تم اقتباس جزء كبير من الشفرة من ملف listobject.c الخاص بلغة بايثون، والذي لم يكن يحتوي على ملف ترخيص. مع ذلك، أتوجه بالشكر إلى تيم بيترز على أجزاء الشفرة التي اقتبستها.
  9. ↑ "ترتيب الأمور في V8 · V8" . v8.dev . تم الاطلاع عليه بتاريخ 21 ديسمبر 2018 .
  10. ↑ "هل دالة sort() مستقرة في Swift 5؟" . منتديات Swift . 4 يوليو 2019. تم الاطلاع عليه في 4 يوليو 2019 .
  11. ↑ "التثبيت في مستودع GitHub "rust-lang/rust"" . GitHub commit . تم الاسترجاع في 29 نوفمبر 2025 .
  12. ↑ ماكلروي، بيتر (يناير 1993). "الفرز التفاؤلي وتعقيد نظرية المعلومات". وقائع الندوة السنوية الرابعة لجمعية ACM-SIAM حول الخوارزميات المنفصلة . الصفحات 467-474 . ISBN  0-89871-313-7.
  13. 1 2 3 "listsort.txt" . شفرة مصدرية بلغة بايثون . 18 مايو 2022. مؤرشفة من الأصل بتاريخ 28 يناير 2016.
  14. ↑ ماكيفر، ديفيد ر. (11 يناير 2010). "فهم خوارزمية فرز تيم، الجزء 1: فرز الدمج التكيفي" . تم الاسترجاع في 5 ديسمبر 2015 .
  15. ↑ بيترز، تيم. "listsort.txt" . مستودع CPython على Git . تم الاطلاع عليه بتاريخ 5 ديسمبر 2019 .
  16. ↑ "openjdk-jdk11u/src/java.base/share/classes/java/util/TimSort.java at master · AdoptOpenJDK/openjdk-jdk11u" . GitHub .
  17. ↑ "cpython/Objects/listobject.c في الإصدار 3.4.10 · python/cpython" . GitHub .
  18. ^ "pypy/rpython/rlib/listsort.py في 7fce1e526e750b4880c7fe61ce9362227ce60a70 · pypy/pypy" . جيثب .
  19. 1 2 3 4 5 قاسمي، إلهي؛ جوجي، فنسنت؛ خليقينجاد، غزال (28 يونيو 2022). التسارع في فرز الدمج الطبيعي سريع النمو . المؤتمر الدولي للزراعة والبيولوجيا الجزيئية 2022. ص 3. doi : 10.4230/LIPIcs.ICALP.2022.68 . 
  20. ^ ريفسجارد شو، ينس كريستيان. وانغ باي (2024). PersiSort: منظور جديد للفرز التكيفي على أساس الثبات (PDF) . CCCG. ص. 2. 
  21. 1 2 دي غو، ستاين؛ روت، يوريان؛ دي بوير، فرانك س.؛ بوبل، ريتشارد؛ هانلي، راينر (2015). "دالة Java.utils.Collection.sort() في OpenJDK معطلة: الجوانب الجيدة والسيئة والأسوأ" . في: كرونينغ، دانيال ؛ باساريانو، كورينا س. (محرران). التحقق بمساعدة الحاسوب - المؤتمر الدولي السابع والعشرون، CAV 2015، سان فرانسيسكو، كاليفورنيا، الولايات المتحدة الأمريكية، 18-24 يوليو 2015، وقائع المؤتمر، الجزء الأول . سلسلة محاضرات في علوم الحاسوب. المجلد 9206. سبرينغر. الصفحات 273-289 . doi : 10.1007/978-3-319-21690-4_16 .  
  22. ↑ دي غوو، ستاين (24 فبراير 2015). "إثبات أن خوارزمية الفرز في أندرويد وجافا وبايثون معيبة (وتوضيح كيفية إصلاحها)" . تم الاطلاع عليه بتاريخ 6 مايو 2017 .
  23. ↑ "المشكلة رقم 23515: منطق خاطئ في دالة merge_collapse الخاصة بـ timsort - متتبع أخطاء بايثون" . bugs.python.org .

للمزيد من القراءة