مرتب سازی پایه ای

مرتب سازی پایه ای یا مرتب سازی مبنایی ( به انگلیسی: Radix sort ) الگوریتمی است که لیستی با اندازهٔ ثابت و اعضایی با طول k را در زمان ( O ( kn انجام می دهد. ورودی ها را به بخش های کوچکی تقسیم می کنیم ( اگر یک کلمه است آن را به حرف هایش می شکنیم و اگر عدد است آن را به ارقامش ) سپس ابتدا لیست را بر اساس کم ارزش ترین بیت ( حرف یا رقم ) مرتب می کنیم، سپس بر اساس دومین بیت، تا در نهایت بر اساس پرارزش ترین بیت. به این ترتیب پس از k مرحله لیست مرتب می شود. این روش مرتب سازی پایدار است و در تهیهٔ واژه نامه ها و مرتب سازی اعداد استفاده می شود. این مرتب سازی به کار هرمان هولریث در سال ۱۸۸۷ روی ماشین های جدول بندی بر می گردد.
بیشتر کامپیوترهای دیجیتال در داخل، اطلاعاتشان را به صورت نمایش الکترونیکی از اعداد دودویی نشان می دهند، پس پردازش ارقام اعداد صحیح با نمایش دودویی خیلی راحت تر است. دو دسته از مرتب سازی های مبنایی عبارت است از: مرتب سازی مبنایی کم ارزش ترین رقم و مرتب سازی مبنایی پر ارزش ترین رقم. مرتب سازی های مبنایی کم ارزش ترین رقم کم ارزش شروع می کنند و به طرف رقم پرارزش می روند، و مرتب سازی های مبنایی پرارزش ترین رقم برعکس عمل می کنند.
معمولاً اعداد صحیحی که با الگوریتم های مرتب سازی پردازش می شوند را «کلیدها» می گویند، که می توانند به تنهایی موجود باشند یا همراه داده های دیگر. مرتب سازی های مبنایی کم ارزش ترین رقم معمولاً اینگونه مرتب می کنند: کلیدهای کوتاه قبل از کلیدهای بلندتر می آید و کلیدهای هم طول هم به صورت لغت نامه ای مرتب می شوند. این با ترتیب معمولی اعداد صحیح منطبق است. مثل ترتیب: ۱، ۲، ۳، ۴، ۵، ۶، ۷، ۸، ۹، ۱۰. مرتب سازی های مبنایی پرارزش ترین رقم ترتیب لغت نامه ای دارند که برای مرتب کردن رشته ها مناسب است. مثل کلمات یا اعداد صحیح با طول ثابت. یک ترتیب مثل»b، c، d، e، f، g، h، i، j، ba «وقتی لغت نامه ای مرتب شود به صورت»b، ba، c، d، e، f، g، h، i، j «در می آید. اگر ترتیب لغت نامه ای برای اعداد صحیح با طول متغیر اعمال شود، آنگاه نمایش اعداد ۱ تا ۱۰ خروجی»۱، ۱۰، ۲، ۳، ۴، ۵، ۶، ۷، ۸، ۹" را پیدا می کند؛ بنابراین در این حالت برای درست مرتب شدن اعداد باید با گذاشتن فاصله از سمت چپ، اعداد کوتاه تر را با اعداد بلندتر هم طول کرد.
یک مرتب سازی مبنایی کم ارزش ترین رقم یک الگوریتم مرتب سازی پایدار سریع است که می تواند برای مرتب سازی کلیدها به ترتیب الفبایی استفاده شود. کلیدها ممکن است یک رشته از حروف یا ارقام داده شده در یک "مبناً باشند. پردازش از کم ارزش ترین رقم ( یعنی رقم سمت راست ) شروع می شود و به پرارزش ترین رقم ( رقم سمت چپ ) می رسد. ترتیبی که رقم ها مورد پردازش قرار می گیرند در مرتب سازی مبنایی کم ارزش ترین رقم برعکس این ترتیب در مرتب سازی مبنایی پرارزش ترین رقم است.