Batcher's even-odd merge sort
Introduction
The odd-even mergesort algorithm for odd-even sorting was developed by Batcher in 1968. The algorithm is not too popular and not too famous. However, it is fairly easy to parallel and its implementation is not too complicated. Personally, I found out about him when I was dealing with MPI and I saw a test task on coursera: write a Batcher sort.
Basic operations
The above code is not ideal in terms of performance, but it is the easiest to understand and understand the algorithm.
In the algorithm, we need the following three abstract operations:
compare-exchange - swap elements if they go out of order.
')
template <class T> void compexch(T& a, T&b) { if (b < a) std::swap(a, b); } perfect shuffle - we divide the array in half and then the first element of the first half - the first as a result, the first element of the second half - the second as a result, the second first half - the third as a result, etc. An array of necessarily even length. In fact, we arrange the elements of the first half in even positions, and from the second - in odd positions.
template <class T> void shuffle(std::vector<T>& a, unsigned int l, unsigned int r) { auto half = (unsigned int) (l + r) / 2; std::vector<T> tmp(a.size()); unsigned int i, j; for (i = l, j = 0; i <= r; i += 2, j++) { tmp[i] = a[l + j]; tmp[i + 1] = a[half + j + 1]; } for (auto i = 0; i < tmp.size(); i++) a[i] = tmp[i]; } perfect unshuffle is the inverse operation of the previous one. Elements occupying even positions are sent to the first half of the result array, odd ones are sent to the second.
template <class T> void unshuffle(std::vector<T>& a, unsigned int l, unsigned int r) { auto half = (unsigned int) (l + r) / 2; std::vector<T> tmp(a.size()); unsigned int i, j; for (i = l, j =0; i<=r; i += 2, j++) { tmp[l + j] = a[i]; tmp[half + j + 1] = a[i + 1]; } for (auto i = 0; i < tmp.size(); i++) a[i] = tmp[i]; } The algorithm itself
As is often the case in posts / articles / books about sorting, we assume that the array arriving at the input has a size equal to the power of two. This will simplify the description of the algorithm and the proof of its correctness. This restriction will be removed later.
Using the entered operations, the algorithm is formulated quite simply. Using the unshuffle operation, we divide the array into two halves. Next, you need to sort each of these halves and then merge it back using the shuffle operation. The algorithm is not just called an even-odd sort of merge - the approach is similar to the well-known merge sort , except that the logic of splitting into parts is different - by the parity of the index, and not just in half.
The simplest implementation using the entered operations:
template <class T> void OddEvenMergeSort(std::vector<T>& a, unsigned int l, unsigned int r) { if (r == l + 1) compexch(a[l], a[r]); // 2 - if (r < l + 2) return; // 1 - , unshuffle(a, l, r); // auto half = (unsigned int) (l + r) / 2; OddEvenMergeSort(a, l, half); OddEvenMergeSort(a, half + 1, r); // shuffle(a, l, r); // for (auto i = l + 1; i < r; i += 2) compexch(a[i], a[i + 1]); auto halfSize = (r - l + 1) / 2 - 1; //* for (int i = l + 1; i + halfSize < r; i++) //* compexch(a[i], a[i + halfSize]); //* } Comment
If you, like me, read about this algorithm in Sedgvik in "Fundamental Algorithms in C ++", then you may notice that in the OddEvenMergeSort function it does not have lines marked with "*". I do not know a typo. However, the algorithm given in his book is wrong, for example, on the string "ABABABAB".
After the first unshuffle call, we get “AAAABBBB”. Further we are called recursively for the “AAAA” and “BBBB” parts. We assume that the algorithm works correctly. Then after the calls we will get the “AAAA” and “BBBB” parts. Make a shuffle, get “ABABABAB”. Pairwise comparison will degenerate into a 4-fold challenge call compexch ("A", "B"), which will not change anything.
Three added lines solve this problem. In the future, if there is time, I will describe why.
After the first unshuffle call, we get “AAAABBBB”. Further we are called recursively for the “AAAA” and “BBBB” parts. We assume that the algorithm works correctly. Then after the calls we will get the “AAAA” and “BBBB” parts. Make a shuffle, get “ABABABAB”. Pairwise comparison will degenerate into a 4-fold challenge call compexch ("A", "B"), which will not change anything.
Three added lines solve this problem. In the future, if there is time, I will describe why.
Description
The principle of operation is practically no different from the merge sort , however, the merge operations are performed completely differently. If in merge sort we get two indices - in the first and in the second half of the array, where the halves are already sorted, and at each step we just put in the result the smallest of the current in each half, here we just do the shuffle operation, and then pairwise compare the resulting array.
How to start?
Just call
OddEvenMergeSort(a, 0, a.size() - 1); How to deal with arrays of length not a power of two?
The easiest way is to add the required number of elements up to the power of two, which are a priori more (or less) of any element in the source array.
The second approach is this.
Since any number can be represented as a sum of powers of two, then split the array into such subarrays, sort them separately by sorting Batcher and merge using an operation similar to the merge in merge sort
In this case, small subarrays can be sorted by another algorithm, which, for example, does not require recursive calls.
Work example
AGINORSTAEELMPXY AIOSAEMXGNRTELPY AOAMISEX AAOM AA MO AMAO AAMO IESX EI SX ESIX EISX AEAIMSOX AAEIMOSX GREPNTLY GERP EG PR EPGR EGPR NLTY LN TY LTNY LNTY ELGNPTRY EGLNPRTY AEAGELINMPORSTXY AAEEGILMNOPRSTXY Source: https://habr.com/ru/post/261777/
All Articles