ثبات در مرتب سازی یا مرتب سازی با ثبات، به الگوریتم هایی گفته می شود که نظم نسبی بین رکورد ها را با کلید های (ارزش) یکسان حفظ می کنند. اگر تمام کلید ها متفاوت هستند ، پس تمایز ضروری نیست ولی اگر کلید های یکسانی وجود دارند، پس یک الگوریتم مرتب سازی زمانی با ثبات یا پایدار است که هروقت که دو رکورد با یک کلید وجود داشت (به عنوان مثال R و S ) و R در لیست اصلی قبل از S آمده بود، آنگاه R در لیست مرتب شده هم قبل از S بیاید. هنگامی که عناصر یکسان، غیر قابل تمایز و تشخیص هستند، در داده هایی که کل عنصر، کلید است، "پایداری" مطرح نیست. به مثال زیر توجه کنید :

(6, 5) (1, 3) (7, 3) (2, 4)

در داده های بالا دو جواب محتمل است که یکی نظم نسبی رکورد در کلید های یکسان را حفظ می کند و دیگری که این چنین نیست :
(6, 5) (2, 4) (1, 3) (7, 3) حفظ نظم :
(6, 5) (2, 4) (7, 3) (1, 3) تغییر نظم : 
الگوریتم های نا پایدار ممکن است نظم نسبی عناصر را تغییر دهند ولی الگوریتم های پایدار اینگونه نیستند. الگوریتم های نا پایدار را میتوان با گسترش و دستکاری الگوریتم مقایسه به الگوریتم های پایدار تبدیل کرد. برای مثال الگوریتم "مرتب سازی حبابی" یک الگوریتم پایدار و الگوریتم "مرتب سازی انتخابی" نا پایدار است.

wikipedia.org