login/register

Snip!t from collection of Alan Dix

see all channels for Alan Dix

Snip
summary

Greed Sort: An Optimal External Sorting Algorithm for Mu...
Mark H. Nodine and Jeffrey Scott Vitter
March 1991
Abstract:
We present an optimal deterministic algorithm for extern ...

Brown CS: Tech Report CS-91-20
http://www.cs.brown.edu/publications/techreports/reports/CS-91-20.html

Categories

/Channels/AVL trees

[ go to category ]

For Snip

loading snip actions ...

For Page

loading url actions ...

Greed Sort: An Optimal External Sorting Algorithm for Multiple Disks

Mark H. Nodine and Jeffrey Scott Vitter

March 1991

Abstract:

We present an optimal deterministic algorithm for external sorting on multiple disks. Our measure of performance is the number of input/output (I/O) operations. In each I/O, each disk can simultaneously transfer a block of data. Our algorithm improves upon a recent randomized optimal algorithm and the (non-optimal) commonly used technique of disk striping. The code is simple enough for easy implementation.

HTML

<h2>Greed Sort: An Optimal External Sorting Algorithm for Multiple Disks</h2> <h3>Mark H. Nodine and Jeffrey Scott Vitter</h3> <h4>March 1991</h4> <h3>Abstract:</h3> We present an optimal deterministic algorithm for external sorting on multiple disks. Our measure of performance is the number of input/output (I/O) operations. In each I/O, each disk can simultaneously transfer a block of data. Our algorithm improves upon a recent randomized optimal algorithm and the (non-optimal) commonly used technique of disk striping. The code is simple enough for easy implementation.