  In this paper we present a framework for designing algorithms in shared
memory of GPUs without incurring memory bank conflicts. Using our framework we
develop the first comparison-based shared memory sorting algorithm that incurs
no bank conflicts. It can be used as a subroutine for GPU sorting algorithms to
replace current use of sorting networks in shared memory. Using our bank
conflict free shared memory sorting subroutine as a black box, we design
BCFMergesort, an algorithm for merging sorted streams of data that are larger
than shared memory. Our algorithm performs all accesses to global memory in
coalesced manner and incurs no bank conflicts during the merge.
