Talk:Batcher odd–even mergesort

GPUGems

It is popularised by the first GPU Gems book

I don't find anything about sorting on GPU in GPUGems1. I think the author meant GPUGems2 instead. There is a chapter about exactly this topic. However, in meantime both books are available for free: GPUGems1, GPUGems2 --Coolcat42 (talk) 19:59, 4 January 2009 (UTC)

Missing Algorithm Explanation Section

The code example reveals all... to those that speak Python. We need a basic explanation in English Friendly Person (talk) 00:49, 5 May 2011 (UTC)

Not at all, running gives

   RuntimeError: maximum recursion depth exceeded  — Preceding unsigned comment added by 94.208.248.165 (talk) 13:03, 30 June 2011 (UTC) 

I corrected the code, tested with

def listminus (one, subtract):
    return [x for x in one if x not in subtract]

def rand_perm (i):
    rv = []
    for j in range (0, 2**i):
        rv.append (random.choice (listminus (range(0,2**i), rv)))
    return rv

def sorted (l):
    for i in range (0, len(l)-1):
        if l[i] > l[i+1]:
            return False

    return True

for it in range (0, 300):
    data = rand_perm (5)
    oddeven_merge_sort (data)
    if not sorted (data):
        print data
    else:
        print "."

Kasterma (talk) 14:19, 30 June 2011 (UTC)

Algorithm only for power of two number of elements

I tried the code example and it does not work (IndexError: list index out of range), because the number of elements is not a power of two. The 2 is missing.

How could the algorithm work for lists of arbitrary length? CvJ1987 (talk) 12:48, 23 October 2011 (UTC)

You can pretend to sort a list that has the length of the next power of two. But remember the real size and in every compare_and_swap-function you must check if b >= realCount. In that case you simply don't swap the items. Popelmaus (talk) 08:42, 27 April 2012 (UTC)

Infobox: stated time complexity labelled space complexity

The infobox dubs a space complexity time complexity: this looks off. 94.220.51.28 (talk) 00:15, 28 March 2021 (UTC)