مرتب‌سازی مجاور-نگاشت
مرتب‌سازی مجاور-نگاشت (به انگلیسی: ProxmapSort) یک نوع الگوریتم مرتب‌سازی است که با دسته‌بندی آرایه ای از داده‌ها یا کلیدها به چند «زیر آرایه» (که در مرتب‌سازی سطلی، سطل نامیده می‌شوند) انجام می‌شود.
ریشهٔ نام این الگوریتم از «مجاورت» و «نگاشت» می‌آید. با یک «مجاورت نگاشتی» که برای هر کلید K شروع زیر آرایه (سطل) را نشان می‌دهد به طوری که K در ترتیب مرتب نهایی قرار گیرد. کلیدها با استفاده از روش مشابه در مرتب‌سازی درجی در هر سطل درج می‌شوند.
اگر کلیدها بین زیر آرایه‌ها «خوب توزیع شده» باشند، مرتب‌سازی در زمان خطی رخ می‌دهد.
می‌توان گفت این الگوریتم ترکیبی از مرتب‌سازی سطلی و مبنایی است.
پس از اتمام مرتب‌سازی مجاور-نگاشت، در صورتی که کلیدها خوب توزیع شده باشند، جستجوی مجاور-نگاشت می‌تواند کلید را در formula_1 پیدا کند.
این دو الگوریتم در اواخر دهه ۱۹۸۰ توسط پروفسور توماس در دانشگاه کالیفرنیا، ارواین اختراع شد.
فرض کنید آرایه A با "n" تا کلید داده شده‌است:
توجه: «کلیدها» همچنین ممکن است شامل داده‌های دیگری باشد، به عنوان مثال آرایه ای از اشیاء دانشجویی که شامل کلید به علاوه شناسه و نام دانشجو می‌باشد. این امر باعث می‌شود ProxMapSort برای سازماندهی گروه‌های اشیاء، نه فقط خود کلیدها، مناسب باشد.
یک آرایه کامل را در نظر بگیرید: A ["0" تا "n-1"] با کلید "N." بگذارید "من" یک فهرست از کلیدهای A. طبقه‌بندی A در آرایه A2 با اندازه مساوی باشم.
عملکرد کلید نقشه به صورت MapKey (کلید) = طبقه (K) تعریف شده‌است.
// compute hit counts for i = 0 to 11 // where 11 is n for i = 0 to 12 // where 12 is A.length
runningTotal = 0; // compute prox map – location of start of each subarray for i = 0 to 11
for i = 0 to 12 // compute location – subarray – in A2 into which each item in A is to be placed
for I = 0 to 12; // sort items for i = 0 to 12 // insert each item into subarray beginning at start, preserving order ! e end of A2 is found, and insertion not made | )
ProxmapSearch از آرایه proxMap تولید شده توسط ProxmapSort که قبلاً انجام شده‌است استفاده می‌کند تا بتواند کلیدها را در آرایه مرتب شده A2 در زمان ثابت پیدا کند. function mapKey(key)
محاسبات H , P و L همه را در نظر می‌گیرد formula_4 زمان. هر یک با یک گذر از یک آرایه محاسبه می‌شود، با زمان ثابت صرف شده در هر مکان آرایه.
داشتن یک عملکرد خوب MapKey برای جلوگیری از بدترین حالت ضروری است. ما باید چیزی در مورد توزیع داده‌ها بدانیم تا یک کلید خوب به وجود بیاید.پیاده‌سازی کد JavaScript:  Array.prototype.ProxmapSort = function()
از آنجا که ProxmapSort یک نوع مقایسه نیست، محدودیت پایین Ω ("n" log "n") غیرقابل استفاده است. سرعت آن را می‌توان به این که نمی مبتنی بر مقایسه و با استفاده از آرایه به جای اشیاء پویا اختصاص داده و اشاره گر است که باید دنبال شود، مانند این است که با زمانی که با استفاده از یک انجام منسوب درخت جستجوی دودویی.
ProxmapSort امکان استفاده از ProxmapSearch را فراهم می‌کند. علی‌رغم زمان ساخت O (n)، ProxMapSearch با این کار می‌کند formula_1 زمان دسترسی متوسط، و آن را برای بانکهای اطلاعاتی بزرگ بسیار جذاب می‌کند. اگر نیازی به به روزرسانی داده‌ها نباشد، زمان دسترسی ممکن است این عملکرد را نسبت به سایر انواع مبتنی بر مرتب‌سازی غیر مقایسه مقایسه کند.
مانند ProxmapSort، سطل مرتب کردن بر اساس به‌طور کلی در یک لیست از "n" ورودی عددی بین صفر و برخی از کلید حداکثر یا ارزش "M" و تقسیم وسیعی ارزش به "n" سطل هر یک از اندازه "M" / "N" عمل می‌کند. اگر هر سطل با استفاده از مرتب‌سازی درج طبقه بندی شده باشد، ProxmapSort و مرتب‌سازی سطل می‌توانند در زمان خطی پیش‌بینی شده اجرا شوند. با این حال، عملکرد این نوع تنزل با خوشه (یا بیش از حد چند سطل با بیش از حد بسیاری از کلیدهای)؛ اگر بسیاری از مقادیر در نزدیکی اتفاق بیفتد، همه در یک سطل واحد قرار می‌گیرند و عملکرد به شدت کاهش می‌یابد. این رفتار همچنین برای ProxmapSort حائز اهمیت است: اگر سطل‌ها خیلی بزرگ باشند، عملکرد آن به شدت کاهش می‌یابد.