bitonic sort Algorithm
The bitonic sort algorithm is a parallel sorting algorithm that is specifically designed for efficient implementation on parallel processors, particularly those with a parallel architecture such as GPUs or distributed computing clusters. The algorithm is based on the concept of a bitonic sequence, which is a sequence of numbers that is first monotonically increasing and then monotonically decreasing, or vice versa. For example, the sequence {1, 3, 7, 8, 6, 5, 2} is a bitonic sequence. Bitonic sort works by successively building up a bitonic sequence from smaller subsequences and then merging them into a fully sorted sequence.
The algorithm operates in two main stages: bitonic sequence creation and bitonic merge. In the first stage, the input sequence is divided into pairs of elements, and each pair is sorted independently. Then, pairs of these sorted pairs are merged to create bitonic sequences of length 4. This process is repeated, merging pairs of bitonic sequences to form larger bitonic sequences, until a single bitonic sequence is obtained. In the second stage, the bitonic merge operation is performed on this sequence to produce a fully sorted sequence. The bitonic merge operation works by comparing and swapping elements of the sequence such that the resulting sequence is split into two bitonic subsequences, one containing all elements less than or equal to the median and the other containing all elements greater than the median. This process is recursively applied to both subsequences until the base case of a sorted pair is reached. The overall complexity of the bitonic sort algorithm is O(n log^2 n), where n is the number of elements in the sequence to be sorted.
# Python program for Bitonic Sort. Note that this program
# works only when size of input is a power of 2.
# The parameter dir indicates the sorting direction, ASCENDING
# or DESCENDING; if (a[i] > a[j]) agrees with the direction,
# then a[i] and a[j] are interchanged.
def compAndSwap(a, i, j, dire):
if (dire == 1 and a[i] > a[j]) or (dire == 0 and a[i] < a[j]):
a[i], a[j] = a[j], a[i]
# It recursively sorts a bitonic sequence in ascending order,
# if dir = 1, and in descending order otherwise (means dir=0).
# The sequence to be sorted starts at index position low,
# the parameter cnt is the number of elements to be sorted.
def bitonic_merge(a, low, cnt, dire):
if cnt > 1:
k = int(cnt / 2)
for i in range(low, low + k):
compAndSwap(a, i, i + k, dire)
bitonic_merge(a, low, k, dire)
bitonic_merge(a, low + k, k, dire)
# This function first produces a bitonic sequence by recursively
# sorting its two halves in opposite sorting orders, and then
# calls bitonic_merge to make them in the same order
def bitonic_sort(a, low, cnt, dire):
if cnt > 1:
k = int(cnt / 2)
bitonic_sort(a, low, k, 1)
bitonic_sort(a, low + k, k, 0)
bitonic_merge(a, low, cnt, dire)
# Caller of bitonic_sort for sorting the entire array of length N
# in ASCENDING order
def sort(a, N, up):
bitonic_sort(a, 0, N, up)
if __name__ == "__main__":
a = []
n = int(input().strip())
for i in range(n):
a.append(int(input().strip()))
up = 1
sort(a, n, up)
print("\n\nSorted array is")
for i in range(n):
print("%d" % a[i])
