Batcher odd–even mergesort
id:
batcher-odd-even-mergesort-0-8257462
title:
Batcher odd–even mergesort
text:
Batcher's odd–even mergesort
is a generic construction devised by Ken Batcher for sorting networks of size O(n (log n)2) and depth O((log n)2), where n is the number of items to be sorted. Although it is not asymptotically optimal, Knuth concluded in 1998, with respect to the AKS network that "Batcher's method is much better, unless n exceeds the total memory capacity of all computers on earth!" It is popularized by the second GPU Gems book, as an easy way of doing reasonably efficient sorts on
brand slug:
wiki
category slug:
encyclopedia
description:
original url:
https://en.wikipedia.org/wiki/Batcher_odd%E2%80%93even_mergesort
date created:
date modified:
2023-12-11T01:23:59Z
main entity:
{"identifier":"Q4868734","url":"https://www.wikidata.org/entity/Q4868734"}
image:
{"content_url":"https://upload.wikimedia.org/wikipedia/commons/4/4c/Batcher_Odd-Even_Mergesort_for_eight_inputs.svg","width":356,"height":288}
fields total:
13
integrity:
14