سلام
الگوریتم مرتب سازی پایدار الگوریتمی است که ترتیب مقادیر مساوی را بعد از مرتب شدن همچنان حفظ می کندمثلا[tex]8_a,3,8_b,4,8_c[/tex] که از اندیس زیرین برای متمایز کردن مقادیر مساوی استفاده کردیم حال اگر یک الگوریتم مرتب سازی پایدار را بکار ببریم خواهیم داشت.[tex]3\: ,\: 4\: ,\: 8_a\: ,\: 8_b\: ,\: 8_c[/tex] یعنی باز [tex]8_a[/tex] قبل از [tex]8_b[/tex] و ان هم قبل از [tex]8_c[/tex] است.در غیر این صورت الگوریتم مرتب سازی ناپایدار است مثلا ترتیب [tex]3\: ,\: 4\: ,\: 8_b\: ,\: 8_c\: ,\: 8_a[/tex] را تولید می کند.
الگوریتم مرتب سازی درجا الگوریتمی است که از فضای کمکی غیر وابسته به اندازه ی ورودی استفاده می کند.مثلا یک گونه ی پیاده سازی(معمول) مرتب سازی heapsort که از همان ارایه ورودی استفاده می کند و نیازی به حافظه ی کمکی ندارد یا بهتر بگیم نیازی به حافظه ی کمکی وابسته به تعداد ورودی ندارد مثلا ممکنه از چند متغیر هم استفاده کند. ولی اگر حافظه ی کمکی وابسته به ورودی باشد غیر درجا است مثلامرتب سازی ادغامی که نیاز به فضای کمکی [tex]O(n)[/tex] دارد پس وابسته به ورودی (n ) است.البته ممکنه برای یک الگوریتم خاص هم نوع متعادل ان را پیاده سازی کرد و هم نوع غیر متعادل . درباره ی درجا و غیر درجا بودن هم ممکنه پیاده سازی مختلف برای یک الگوریتم خاص مقدار فضایی کمکی متفاوتی داشته باشند.ولی تعریف متعادل بودن یا غیر متعادل بودن و درجا یا غیر درجا بودن ثابت است و با توجه به یک پیاده سازی برای یک الگوریتم مرتب سازی میتوان ان را بررسی کرد.