مرتب ساز بایتونیک

مرتب ساز ادغامی بایتونیک الگوریتمی موازی برای مرتب سازی است که از آن برای ساخت شبکه های مرتب سازی نیز استفاده می شود. این الگوریتم را کِن بچر ( ken batcher ) ابداع کرده است. شبکه های مرتب سازی به دست آمده از O ( n l o g ( n ) 2 ) مقایسه کننده تشکیل شده و تأخیری به میزان O ( l o g ( n ) 2 ) دارند که n تعداد مواردی است که باید مرتب شوند.
توالی مرتب شده یک توالی یکنواخت غیر کاهشی ( یا غیر افزایشی ) است. توالی بایتونیک توالی ای با x 0 ≤ … ≤ x k ≥ … ≥ x n − 1 برای برخی مقادیر k، که مقادیر آن در محدوده ۰ ≤ k < n قرار دارند، یا شیفت دورانی این توالی است.
آنچه در ادامه می آید یک شبکهٔ مرتب سازی با ۱۶ ورودی است:
۱۶ عدد در ورودی های انتهای سمت چپ وارد شده، روی هر یک از ۱۶ سیم افقی لغزیده و از خروجی های انتهای سمت راست خارج می شوند. این شبکه به منظور مرتب کردن اجزا طوری که بزرگترین عدد در پایین باشد طراحی شده است.
فلش ها همان مقایسه کننده ها هستند. هرگاه دو عدد به دو انتهای یک فلش می رسند، با یکدیگر مقایسه شده تا تضمین شود که فلش به سمت عدد بزرگتر اشاره دارد. چنانچه بدون ترتیب باشند، جایشان با یکدیگر عوض می شود. جعبه های رنگی تنها برای ترسیم هستند و تأثیری بر الگوریتم ندارند.
جعبه های قرمز ساختار یکسانی دارند: هر ورودی در نیمهٔ بالایی با ورودی متناظر در نیمهٔ پایینی مقایسه می شود، که تمام فلش ها رو به پایین ( قرمز تیره ) یا همه رو به بالا ( قرمز روشن ) هستند. اگر ورودی ها به فرم توالی بایتونیک صورت گیرند، خروجی به فرم دو توالی بایتونیک خواهد بود. به این شکل که نیمهٔ بالایی بایتونیک و نیمهٔ پایینی نیز بایتونیک است، به گونه ای که هر جزء نیمهٔ بالایی کمتر یا مساوی هر جزء نیمهٔ پایینی است ( برای قرمز تیره ) یا برعکس ( برای قرمز روشن ) . این قضیه چندان بدیهی نیست، اما می توان با در نظر گرفتن تمام حالت هایی که ورودی های مختلف ممکن است مقایسه شوند و با استفاده از اصل صفر و یک آن را بررسی کرد.
با ترکیب جعبه های قرمز جعبه های آبی و سبز تشکیل می شوند. هر یک از این جعبه ها ساختار مشابهی دارد: جعبه قرمز به کل توالی ورودی اعمال می شود، سپس به هر نیمهٔ نتیجه، و سپس به هر نیمهٔ هر یک از آن نتایج و غیره. تمام فلش ها به سمت پایین ( آبی ) یا به سمت بالا ( سبز ) اشاره دارند. این ساختار با عنوان شبکهٔ پروانه ای شناخته می شود. چنانچه ورودی به این جعبه بایتونیک باشد خروجی کاملاً به ترتیب افزایشی ( آبی ) یا کاهشی ( سبز ) مرتب می شود. اگر عددی وارد جعبه آبی یا سبز شود، اولین جعبه قرمز آن را به طرف نیمهٔ صحیح لیست مرتب می کند. سپس از یک جعبه قرمز کوچکتر رد شده که آن را به طرف یک چهارم صحیح از لیست آن نیمه، مرتب می کند. این روند تا جایی ادامه می یابد که به مکان درست مرتب شود؛ بنابراین، خروجی جعبه سبز یا آبی کاملاً مرتب می شود.