Bitonic Merge pada Shuffle-Exchange Nework
Teorema 10.6. Sebuah daftar dengan n = 2k buah elemen yang tidak terurut dan dapat diurutkan dalam waktu dengan jaringan
komparator menggunakan skema interkoneksi shuffle-exchange secara exclusive (Stone, 1971)
Stone menyadari bahwa Pengurut Bitonic milik Batcher ini selalu membandingkan elemen-elemen dengan index yang berbeda tepat 1 bit pada bentuk biner nya. Dengan perfect shuffle, akan memperjalankan elemen pada posisi i ke posisi yang ditemukan., dengan memutar tampilan biner dari i satu bit ke kiri. Dengan demikian dua buah index yang tampilan biner nya berbeda tepat 1 bit dapat diperjalankan ke komparator yang sama dengan cara melakukan sejumlah shuffle tertentu.
Gambar berikut ini menunjukkan bagaimana bitonic merge dapat diimplementasi dengan menggunakan skema interkoneksi shuffle-exchange secara ekslusif.
Gambar 10-13
Sangat berbeda dengan Gambar 10-10, dimana interkoneksi antar komparator nya bervariasi dari tahap ke tahap lainnya. Keseluruhan proses pengurutan dapat diselesaikan dengan menggunakan interkoneksi shuffle-exchange. Kedua algoritma membutuhkan k bitonic merge untuk mengurutkan 2k elemen, tetapi ketika merge ke-i di algoritma Batcher membutuhkan i langkah untuk total k(k+1)/2,
Algoritma
‘
