(۲۶ دى ۱۳۹۵ ۰۲:۲۳ ب.ظ)Jooybari نوشته شده توسط:  سلام. وقت بخیر.
پایداری در مورد ترتیب داده‌های با کلید برابر عنوان میشه. اگه دو عنصر، کلید برابر داشته باشن، اونی که تو آرایه زودتر اومده، باید تو آرایه مرتب هم زودتر بیاد. با توجه به نحوه ادغام دو آرایه مرتب، چون دو آرایه‌ای که ادغام میشن مجاور هستن، اون ترتیب رو میشه حفظ کرد. یعنی اگه دو کلید با مقدار برابر تو دوتا آرایه مجاور دیدیم، اول سمت چپی رو قرار میدیم.

در مورد مرتب‌سازی در حافظه، در نظر بگیرید که حافظه موقتمون محدوده و قراره یه آرایه بزرگی که تو حافظه دائم ذخیره شده رو قصد داریم مرتب کنیم. میدونیم که سرعت خوندن و نوشتن حافظه دائم خیلی کمه و خوندن یه عدد با یه بلوک پشت سر هم زمان برابری داره. پس باید دفعات خوندن از حافظه دائم رو کم کنیم و بلوک، بلوک بخونیم. روشی که الگوریتم مرتب سازی ادغامی داره، با این فرضیات وفق پذیره. هم مرتبه زمانی بهینه (با توجه به مقایسه‌ای بودن) داره و هم میتونه دفعات خوندن از حافظه رو کمینه کنه.