الگوریتم Timsort

در این مقاله‌ به بررسی مفصل و جامع الگوریتم تیم‌سورت می‌پردازیم.

بعد از کمی مقدمه، معرفی الگوریتم و بررسی یک تاریخچه‌ی کوتاه، گام به گام الگوریتم و تمامی سیاست‌هایی که در آن بکار گرفته شده‌اند را بررسی می‌کنیم و توابعی در CPython که در هر گام، وظیفه مرتب کردن یک لیست را دارند (list.sort) معرفی می‌کنیم.

مقدمه و معرفی

در دنیای علوم کامپیوتر، مرتب‌سازی یک عملیات اساسی با کاربرد‌های بی‌شمار است. در میان انبوهی از الگوریتم‌های مرتب‌سازی، یکی از الگوریتم‌ها به دلیل کارایی، تطبیق‌پذیری و طراحی زیبا متمایز شده است: الگوریتم تیم‌سورت. این الگوریتم که توسط تیم پیترز برای زبان برنامه نویسی پایتون توسعه یافته است، به سنگ بنای پیاده‌سازی مرتب‌سازی در زبان‌ها و محیط‌های مختلف برنامه‌نویسی تبدیل شده است.

ترکیب منحصر به فرد مرتب‌سازی ادغامی (Merge Sort) و مرتب‌سازی درجی (Insertion Sort) به همراه‌ بهینه‌سازی‌های مخصوص روی هر الگوریتم و بهینه‌سازی‌های تطبیقی‌، تیم‌سورت را به یکی از پیچیده‌ترین، کاربردی‌ترین و یکی از بهینه‌ترین الگوریتم‌های مرتب‌سازی تبدیل کرده است.

تاریخچه

الگوریتم تیم‌سورت، در سال ۲۰۰۲ توسعه یافت. این الگوریتم از نسخه‌ی 2.3 پایتون تا حدود بیست سال، الگوریتم استاندارد مرتب‌سازی در پایتون بود و از نسخه‌ی 3.11.1 به دلیل تغییراتی که در سیاست‌های ادغام آن بوجود آمد، الگورتیمی به اسم Powersort بر پایه‌ی تیم‌سورت، جایگزین آن شد.

الگوریتم تیم‌سورت در

• زبان Java SE 7
• سیستم عامل Android
• زبان GNU Octave
• انجین V8
• زبان Swift
• زبان Rust

پیاده‌سازی شده است.

چراها

تیم‌ پیترز این الگوریتم را اینگونه توصیف می‌کند:

A non-recursive adaptive stable natural merge sort / binary insertion sort hybrid algorithm

• چرا non-recursive؟
  چون طبق گفته‌ی تیم پیترز: «به طور خلاصه، روتین اصلی یک بار از سمت چپ تا راست، آرایه را طی، Run‌ها را شناسایی و هوشمندانه‌ آنها را با هم ادغام می‌کند» (مفهوم Run در ادامه توضیح داده‌ خواهد شد.)
• چرا adaptive؟
  چون این الگوریتم با توجه به طول و ترتیب‌های از قبل موجود در آرایه، و همچنین بر اساس اندازه‌‌ی Runهای پیدا شده، تصمیماتی می‌گیرد تا از الگوریتم بهتری برای آن موقعیت استفاده کند.
• چرا stable؟
  چون این الگوریتم، ترتیب عناصر یکسان در آرایه‌ی اولیه را حفظ می‌کند. برای مثال اگر لیستی از این اسامی داشته باشیم:

و آنرا بخواهیم بر اساس حرف اول کلمات مرتب کنیم، چنین چیزی می‌گیریم:

اگر دقت کنید در لیست اولیه، straw قبل از spork آمده بود و در لیست مرتب شده هم همین ترتیب حفظ شد. به این نگهداری ترتیب اولیه‌ی عناصر، پایداری الگوریتم مرتب‌سازی می‌گویند.

• چرا hybrid؟
  چون این الگوریتم از ترکیب دو الگوریتم Merge Sort و Binary Insertion Sort برای مرتب سازی استفاده می‌کند.

مقایسه

مقایسه‌ی کلی بین پیچیدگی زمانی الگوریتم‌های TimSort و Merge Sort و Quick Sort و Heap Sort چنین چیزیست:

اما این تحلیلِ کلی، یک سری جزئیات راجع به پیچیدگی زمانی الگوریتم را پنهان می‌کند که آن یکconstant factor اثرگذار در میزان پیچیدگی الگوریتم است.

• برای مثال در الگوریتم Quick Sort انتخاب مقدار left و right و pivot اثرگذاراند و در nهای کوچک سرعت را پایین می‌آورد.
• در الگوریتم Merge Sort هم فضایی به اندازه‌ی n + m برای ادغام کردن آرایه‌ها آن هم به صورت بازگشتی و تعداد زیاد نیاز دارد. همچنین این الگوریتم، یک الگوریتم بازگشتی‌ست و درخت بازگشتی و یک system stack برای اجرا نیاز دارد.
• بخاطر جابجایی‌هایی در الگوریتم Heap Sort انجام می‌شود، Locality of Reference در آن بارها نقض شده و پیشبینی‌های پردازنده‌ برای کش کردن داده‌ها را تضعیف می‌کند.

پس اگر بتوانیم این constant factor را کاهش دهیم می‌توانیم سرعت بیشتری از O(nlgn) بگیریم.

بررسی الگوریتم Binary Insertion Sort

پیچیدگی زمانی Insertion Sort برابر با O(n^2) است و constant factor آن بسیار بسیار کوچک است؛ چون اولا inplace عمل می‌کند (پس نیازی به فضای اضافه ندارد) و ثانیا فقط بین عناصر آرایه پیمایش انجام می‌دهد (پس Locality of Reference هم در آن بسیار خوب است و پردازنده می‌تواند داده‌ها را کش کند.) در تحلیل‌های انجام شده روی الگوریتم‌ها، این الگوریتم روی تعداد ورودی ۶۴ و پایین‌تر، از الگوریتم‌های دیگر مرتب سازی سریع‌تر عمل می‌‌کند.

الگوریتم Binary Insertion Sort بجای جستجوی خطی در آرایه (با پیچیدگی O(n)) در آن جستجوی دودویی انجام داده و در زمان لوگاریتمی (O(lgn)) مکان صحیح آیتم را پیدا می‌‌کند (علت استفاده از این الگوریتم در ادامه روشن خواهد شد.)

با تعویض نوع جستجوی‌ این الگوریتم میزان پیچیدگی آن (حالت مورد انتظار و در بدترین حالت) تغییری نکرده و همان O(n^2) باقی می‌ماند؛ اما در CPython مقایسه‌ها (بخاطر ماهیت dynamic typed بودن زبان) نسبت به جابجا کردن آبجکت‌ها بسیار وحشتناک کند‌تر هستند.

جابجا کردن آبجکت‌ها صرفا کپی کردن ۸ بایت pointer است اما مقایسه‌ها میتوانند بسیار کند باشند (چون ممکن است چند متد در سطح پایتون را صدا بزنند) و حتی در حالات ساده ممکن است بین ۳ یا ۴ تصمیم گرفته بشود:

• تایپ عمل‌وند چپ چیست؟
• تایپ عمل‌وند راست چیست؟
• آیا باید آنها را به یک تایپ مشخص تبدیل کرد؟
• چه کدی برای مقایسه این دو موجود هست؟ و...

پس یک مقایسه ساده باعث تعداد بسیار زیادی C-level pointer dereference، عملیات‌های شرطی و صدا زده شدن توابع می‌شود.

پس اگر ما تعداد مقایسه‌ها کمتر کنیم میتوانیم سرعت مرتب سازی را بیشتر کنیم (که با استفاده ازbinary insertion sort ما تعداد مقایسه‌ها را کم می‌کنیم.)

این مرتب‌ سازی با تابع binarysort در کدهای CPython انجام می‌شود.

ایده

اگر آرایه را به تکه‌های کوچک تقسیم کنیم‌ (برای مثال ۳۲ تا ۶۴ تایی) و سپس آنها را جدا جدا با مرتب‌ سازی درجی مرتب کنیم و سپس همه را ادغام کنیم، می‌توانیم سرعت مرتب سازی را افزایش دهیم. با اینکار:

• از مرتب سازی درجی که برای تعداد کم سریع است استفاده کردیم
• ادغام دو آرایه مرتب شده در زمان O(n) انجام می‌شود
• با این کار ما توانستیم ۵ سطح از درختی در Merge sort تولید می‌شود را کم کنیم

و پیچیدگی تیم‌سورت تا اینجا چنین می‌شود:

که چون اینکه پیچیدگی Binary Insertion Sort در nهای بزرگ کوچک است می‌توان از آن چشم‌پوشی کرد.

حقیقت

در دنیای واقعی و داده‌های واقعی معمولا آرایه‌ها اصطلاحا partially sorted هستند. این به این معناست که تکه‌هایی از آرایه از قبل مرتب هستند؛ برای مثال در این آرایه:

قسمت

از قبل مرتب است.

یا داده‌ها حداقل به صورت صعودی یا نزولی پشت سر هم حضور دارند؛ برای مثال در این آرایه:

قسمت

به صورت صعودی و قسمت

به صورت نزولی مرتب است.

الگوریتم تیم‌سورت این تکه‌های صعودی و یا اکیدا نزولی را در آرایه پیدا می‌کند و آنها را Run می‌نامد و از مرتب بودن اولیه آرایه برای افزایش سرعت استفاده می‌کند.

نتیجه

اگر از حقیقت قبلی استفاده کنیم و آرایه را به قسمت‌هایی صعودی و یا اکیدا نزولی تقسیم کنیم می‌توانیم درخت Merge sort حتی بیشتر از قبل هم کوتاه کنیم، و پیچیدگی را به

تبدیل کنیم. پس هر طول و تعداد Runها بیشتر باشد، مقدار x بیشتر و درخت ادغام ما کوتاه‌تر و الگوریتم سریع‌تر می‌شود.

توضیح Runها

تکه‌هایی از آرایه که از قبل دارای ترتیب هستند، در این الگوریتم یک Run نام می‌گیرند. Runها میتوانند:

• صعودی باشند:

• اکیدا نزولی باشند:

دلیل اینکه یک Run باید نزولی اکید باشد تا یک Run شناخته شود، اینست که الگوریتم تیم‌سورت Run‌های نزولی را به صورت درجا، برعکس می‌کند و اگر در یک Run نزولی (و نه اکیدا نزولی) دو عنصر یکسان وجود داشته باشد، ماهیت stable بودن الگوریتم نقض می‌شود. برای مثال این‌ آرایه:

اگر برعکس شود:

که ترتیب عناصر ۳ عوض شده است. اما اگر اکیدا نزولی باشد دیگر این مشکل وجود نخواهد داشت.

نکته‌ی دیگر اینست که Runها حداقل دو آیتم دارند مگر وقتی که آخرین عضو آرایه را برای Run جدید برگزینیم.

اگر عناصر آرایه رندوم باشند، بعید است که ما Runهای طبیعی (یعنی قسمتی از آرایه که از قبل مرتب شده باشد) بلندی را شاهد باشیم. اگر یک Run طبیعی تعداد عناصرش کمتر از minrun باشد (توضیح داده خواهد شد،) الگوریتم با استفاده از Binray Insertion Sort تعداد آنرا به حداقل اندازه‌ی Run می‌رساند. دلیلی که می‌توانیم از Binray Insertion Sort استفاده کنیم اینست که هر Run خودش مرتب است، پس می‌توان در آن جستجوی دودویی انجام داد.

یک مثال

الگوریتم برای پیدا کردن Runها چنین عمل می‌کند: فرض کنید که اندازه‌ی Runها ۳ تعیین شده است و چنین آرایه‌ای داریم:

از چپ به راست حرکت می‌کنیم ۸ را جدا می‌کنیم و سراغ آیتم بعدی می‌رویم و متوجه می‌شویم که یک Run صعودی داریم:

ادامه ‌می‌دهیم و به عدد ۹ می‌رسیم، چون این Run باید صعودی باشد، و حداقل طول هم ۳ است و ۹ از ۱۲ کمتر است با استفاده از Binary Insertion Sort جایگاه ۹ را پیدا می‌کنیم.

عدد بعدی هم بزرگ‌تر از ۱۲ است و آن را هم به این Run اضافه می‌کنیم:

عدد بعدی، از ۱۷ کمتر است و چون ما حداقل اندازه‌ی یک Run را داریم آنرا دیگر به این Run اضافه نمیکنیم و به سراغ Run بعدی می‌رویم. پس:

و سپس با Binary Insertion Sort:

و چون 11 از 1- بیشتر است و ما حداقل اندازه‌ی یک Run را داریم ابتدا آنرا برعکس:

و به سراغ Run بعدی می‌رویم؛ که Run بعدی هم این است:

که الگوریتم آنرا هم برعکس می‌کند تا صعودی شود:

اگر داده‌ها رندوم باشند، اکثر Runها یک اندازه خواهند داشت که دو خوبی دارد:

1. ادغام کردن Runهایی که اندازه‌ی برابر دارند بسیار بهینه است و
2. ما حداقل توانسته‌ایم اندازه‌ی درخت بازگشتی ادغام را به اندازه‌ی کف lg(minrun) کم کنیم.

برای داده‌های واقعی هم، ما چون Runهای نسبتا بلندی خواهیم داشت توانسته‌ایم کوتاه‌ترین درخت بازگشتی ادغام را داشته باشیم و در نتیجه تعداد ادغام‌ها را کم کنیم. پیدا کردن Runها در آرایه توسط تابع count_run انجام می‌شود.

کدی که به Runهای اضافه شده، عنصر اضافه می‌کند تا به اندازه‌ی minrun برسند:

محاسبه‌ی minrun

محاسبه‌ی minrun بر اساس اندازه‌ی اولیه آرایه، انجام می‌شود:

اگر طول آرایه‌ کمتر از 64 باشد، از Binary Insertion Sort برای مرتب کردن آن استفاده می‌شود.

اگر طول آرایه توانی از ۲ بود، طبق تست‌های انجام شده تمامی اعداد ۸ و ۱۶ و ۳۲ و ۶۴ و ۱۲۸ سرعت یکسانی را به الگوریتم می‌دادند اما مثلا در اندازه‌ی ۲۵۶ تا، جابجا کردن عناصر در مرتب ‌سازی هزینه بردار و در انداز‌ه‌ی ۸ تعداد صدا زده شدن توابع هزینه‌ بردار بود. بعد از کمی مطالعه عدد ۳۲ برای minrun انتخاب شد.

اما بعد از زمان زیادی یک اشکال در انتخاب این عدد پیدا شد، این مثال را ببینید:

که اگر با این تعداد Run ما ادغام را انجام بدهیم، در پایان باید یک آرایه‌ی ۲۰۴۸ عضوی و یک آرایه‌ی ۶۴ عضوی را با هم ادغام کنیم که اصلا خوب نیست. اما اگر عدد ۳۳ را برای minrun انتخاب کنیم ما ۶۴ تا Run با اندازه‌ی ۳۳ داریم که برای ادغام خیلی بهتر است.

سیاستی که برای محاسبه‌ی minrun در پیش گرفته شده است اینست که این مقدار از range(32, 64) به صورتی انتخاب می‌شود که N/minrun یا دقیقا توانی از دو باشد، یا اگر این ممکن نبود، اکیدا کمتر از توان ۲ باشد.
این انتخاب توسط تابع merge_compute_minrun انجام می‌شود.

بهتر کردن استفاده از فضا در ادغام

الگوریتم ادغام در Merge sort الگوریتمی inplace نیست و برای ادغام کردن دو آرایه با طول‌های n و m یک آرایه‌ی جدید به طول n + m نیاز دارد، اما تیم‌سورت برای inplace مرتب کردن و کمتر کردن space overhead الگوریتم مرتب سازی ادغامی از روش بهتری برای ادغام کردن دو Run استفاده می‌کند.

اگر آرایه‌ای به این صورت داشته باشیم:

در این روش جدید ادغام ما یک آرایه‌ی موقت به اندازه‌ی Run کوچک‌تر درست می‌کنیم و عناصر Run کوچک‌تر را در آن کپی می‌کنیم. کپی کردن‌های این چنین هم (یعنی یک تکه از یک آرایه) به بهینه‌ترین حالت در سطح پایین اجرا می‌شوند. پس حالا ما چنین چیزی داریم:

چون آرایه‌ی کوچک‌تر سمت چپ بود، پس از سمت چپ‌ آرایه‌ی موقت و دومین Run شروع به ادغام کردن می‌کنیم. که یعنی:

را باهم مقایسه، و برنده (عنصر کوچک‌تر) را در ایندکس صفر آرایه‌ی A می‌گذاریم. که می‌شود:

سپس:

که می‌شود:

سپس:

که می‌شود:

سپس:

که می‌شود:

سپس:

که می‌شود:

سپس:

که می‌شود:

سپس:

که در اینجا عنصر ۲۲ آرایه‌ی موقت انتخاب می‌شود. چون برای حفظ پایداری الگوریتم مرتب‌ سازی لازم است که بیست و دویی که زودتر آمده انتخاب شود:

وضعیت کنونی ادغام:

و حالا که عناصر آرایه‌ی موقت تمام شده، باقی عناصر باقی مانده سر جای خود هستند و دیگر مقایسه و جابجایی لازم نیست و آرایه به صورت مرتب ادغام شد:

جهت ادغام

در مثال قبلی Run کوچک‌تر در سمت چپ بود و ما ادغام را از سمت چپ Run بزرگ‌تر و آرایه‌ی موقت انجام دادیم، اما اگر چنین حالتی باشد:

ما چنین چیزی داریم:

در این حالت که Run کوچک‌تر در سمت راست بود، ما هم تمام ادغام را از سمت راست انجام می‌دهیم

که می‌شود:

و سپس:

که می‌شود:

و الی آخر...

تابعی که عمل ادغام را شروع می‌کند، تابع merge_collapse است که در ادامه بیشتر راجع به آن توضیح داده خواهد شد.

تکنیک Galloping

چنین سناریویی را تصور کنید: ما این آرایه‌ و Runها را داریم:

در تکنیک Galloping، ما با استفاده از binary search مکان اولین عضو Y را در X پیدا می‌کنیم که می‌بینیم در جایگاه ۴ باید آن را بگذاریم، این یعنی تمامی عناصر قرمز سر جای واقعی و درست خود قرار دارند:

در جایگاه درستی قرار دارند.

همین کار را برای آخرین عنصر X نسبت به Y انجام می‌دهیم که مکان آن در جایگاه پنجم دومین Run است، این یعنی تمامی عناصر قرمز در جایگاه درستی قرار دارند.

پس ما چنین آرایه‌ و Runهایی داریم:

و صرفا باید الگوریتم ادغامی که بالاتر بحث شد را روی این X و Y کوچک‌تر انجام بدهیم که هم سریع‌تر است و هم فضای کمتری استفاده خواهد کرد.

نکته‌ای که در تکنیک Galloping وجود دارد اینست که این روش فقط بعضی وقت‌ها فقط به نفع ماست. به این مثال دقت کنید:

ابتدا مکان ۲ را در X پیدا می‌کنیم که در جایگاه دوم باید قرار بگیرد و سپس مکان ۹ را در Y پیدا می‌کنیم که در جایگاه پنجم باید قرار بگیرد.

که به چنین آرایه‌ای می‌رسیم:

که مشخصا هیچ بهبودی را برای ما نداشت هیچ، بلکه چندین مقایسه اضافه‌ هم با Binary Search انجام داده‌ایم.

مقدار min_gallop

طبق تست‌هایی که تیم پیترز انجام داده است، تعداد عنصری که باید سر جای خودشان باشند، در ابتدای الگوریتم، باید حداقل ۷ تا باشد که این عدد نام min_gallop دارد. این یعنی اگر جایگاه اولین عنصر Y را در X پیدا کنیم و ۷ عنصر در جایگاه خودشان باشند، این تکنیک موثر خواهد بود (همین برای پیدا کردن آخرین عنصر X در Y هم صدق می‌کند.)

در ادغام کردن اگر حالت اول (مکان اولین عنصر Y در X) یا حالت دوم (مکان آخرین عنصر X در Y) بزرگ‌تر مساوی min_gallop بود، از این تکنیک استفاده می‌شود.

بعد از هر بار موفق بودن galloping عدد min_gallop به عنوان یک تشویق برای الگوریتم، یکی کم می‌شود تا در ادامه هم بتوان از galloping استفاده کرد.

حالت عکس هم چنین است که مکان پیدا شده کمتر از min_gallop باشد که یعنی این تکنیک موثر نبوده و از حالت مقایسه‌ی ادغامی ساده، یعنی عنصر به عنصر استفاده می‌شود و عدد min_gallop به عنوان جریمه یکی زیاد می‌شود.

روش galloping در داده‌های واقعی که partially sorted هستند بسیار کارآمد است و تعداد مقایسه‌ها را کمتر می‌کند اما در داده‌های رندوم این روش موثر نیست و از مقایسه‌ی عنصر به عنصر استفاده می‌شود که

• کد ساده‌ای دارد و
• از اصل همجواری (Locality of Reference) به خوبی پیروی می‌کند و پردازنده می‌تواند به خوبی داده‌ها را کش کند.

در الگوریتم gallop کردن از چپ توسط تابع gallop_left و gallop کردن از سمت راست توسط تابع gallop_right انجام می‌شود. این دو تابع انعکاس آئینه‌ای همدیگر هستند.

ساختار MergeState

برای ادغام ساختاری در کد‌هایی که مربوط به الگوریتم تیم‌سورت پیدا می‌شود به اسم MergeState؛ این ساختار اطلاعات مورد نیاز برای توابع ادغام را داراست. اطلاعات دیگری که در این ساختار نگهداری می‌شوند:

• مقدار min_gallop
• اندازه‌ی استک Runها: n
• خود استک Runها: pending
• آرایه‌ی موقت ادغام کردن: temparray و
• سه تابع key_compare و key_richcompare و tuple_elem_compare برای سناریو‌های مختلف مقایسه کردن بین عناصر آرایه.

کد این ساختار اینجا قرار دارد.

جلوگیری از بازگشتی شدن الگوریتم

توابع بازگشتی وقتی که صدا زده می‌شوند، اطلاعات هر بار صدا زده شدن آنها، در در یک stack ذخیره می‌شوند، اما آقای تیم پیترز این الگوریتم را که ماهیت بازگشتی مانندی دارد را غیر بازگشتی نوشته است و برای اینکار از یک stack مخصوص خودش در سطح کد استفاده می‌کند. هر بار که یک Run پیدا می‌شود و اندازه‌ی آن به minrun و یا بیشتر می‌رسد، اطلاعات آن روی stack گذاشته می‌شود.

اگر بخواهیم ساده نگاه کنیم فرض می‌کنیم، خود Run روی استک گذاشته می‌شود اما در واقع فقط آدرس شروع و اندازه‌ی آن روی استک ذخیره می‌شود تا از تکه تکه کردن آرایه و اشغال فضای بیشتر جلوگیری شود.

این استک، نقاط شروع و طول هر Run را در خودش ذخیره می‌کند.

این یعنی: Run عه iام از آدرس base[i] شروع شده وlen[i] تا ادامه دارد و این عبارت همیشه درست است:

برای اینکه اندازه‌ی Runها دقیقا و یا تقریبا با هم برابر بمانند تا الگوریتم‌های ادغام آنها را سریع‌تر ادغام کنند، هر بار که یک Run جدیدی ساخته می‌شود اطلاعات آن روی استک گذاشته می‌شود، دو شرط برای Runهای روی استک چک می‌شوند.

اگر روی استک ما Runهای Xو Y و Z وجود داشته باشند، این شروط باید حفظ شوند:

شرط دوم بر این دلالت دارد که اندازه‌ی Runها از بالا به پایین به صورت صعودی باشد و شرط اول بر این دلالت دارد که وقتی از بالا به پایین می‌رویم طول Runها حداقل با سرعت دنباله‌ی فیبوناچی رشد کنند.

اگر هر کدام از این شروط نقض بشوند، Run عه Y با Run کوچک‌تر از بین X یا Z ادغام می‌شود و شروط دوباره چک می‌شوند و اگر برقرار بودند، الگوریتم به دنبال Run بعدی در آرایه جستجو می‌کند.

برای مثال اگر

هر کدام از X یا Z که کوچک‌تر باشند، با Y ادغام می‌شوند (که الگوریتم X را ترجیح می‌دهد؛ بخاطر اینکه در کش تازگی دارد.)

برای مثال اگر این Runها را داشته باشیم:

ران عه Y با X ادغام می‌شود:

و یا اگر

ران Y با Z ادغام می‌شود:

که در هر دو مثال شرط دوم نقض می‌شود و الگوریتم تا زمانی که این دو شرط درست شوند، به ادغام کردن ادامه می‌دهد و در نهایت، تنها یک Run روی استک باقی می‌ماند که آرایه‌ی مرتب شده‌ی ماست.

تابع merge_collapse مدیریت این شروط را به عهده دارد و انتخاب می‌کند که کدام Runها با هم ادغام شوند و این کار را با تابع merge_at انجام می‌دهد.

عمل ادغام تصمیمات مبنی بر اینکه ادغام باید با galloping شود یا نشود را از نتایج توابع galloping اتخاذ و عملیات ادغام با توجه به شرایط را با کمک توابع merge_lo و merge_hi انجام می‌دهد.

مروری بر Timsort

اگر بخواهیم روی مطالبی که خواندیم مروری داشته باشیم الگوریتم به طول کلی یکبار از سمت چپ شروع به حرکت در آرایه می‌کند، قسمت‌‌هایی که از قبل ترتیبی صعودی یا اکیدا نزولی دارند را شناسایی می‌کند، اگر اندازه‌ی آنها به اندازه‌ی minrun نبود آنها را به صورت مرتب بزرگ‌تر می‌کند تا به minrun برسند و سپس با سیاست‌های خاصی برای ادغام، مانند استفاده از یک آرایه‌ی موقت کوچک، نزدیک نگه داشتن طول Runها برای ادغام و ادغام با استک برای جلوگیری از بازگشتی شدن الگوریتم آنها را با هم ادغام می‌کند.

اسلاید‌های ارائه‌ی الگوریتم

اگه برای ارائه‌ی این الگوریتم به اسلاید نیاز دارید می‌تونید از اسلاید‌های من در اینجا

فایل slides.pdf استفاده کنید.

منابع:

• https://github.com/python/cpython/blob/3.10/Objects/listsort.txt
• https://github.com/python/cpython/blob/3.10/Objects/listobject.c
• https://en.wikipedia.org/wiki/Timsort
• FASTEST Sorting Algorithm (Part I)
• FASTEST Sorting Algorithm (Part II)
• FASTEST Sorting Algorithm (Part III)
• FASTEST Sorting Algorithm (Part IV)