[go: up one dir, main page]

Franceschini et al., 2005 - Google Patents

An in-place sorting with O (n log n) comparisons and O (n) moves

Franceschini et al., 2005

View PDF
Document ID
9253729775065257056
Author
Franceschini G
Geffert V
Publication year
Publication venue
Journal of the ACM (JACM)

External Links

Snippet

We present the first in-place algorithm for sorting an array of size n that performs, in the worst case, at most O (n log n) element comparisons and O (n) element transports. This solves a long-standing open problem, stated explicitly, for example, in Munro and Raman [1992], of …
Continue reading at arxiv.org (PDF) (other versions)

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G06F17/30961—Trees
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30286—Information retrieval; Database structures therefor; File system structures therefor in structured data stores
    • G06F17/30312—Storage and indexing structures; Management thereof
    • G06F17/30321—Indexing structures
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30067—File systems; File servers
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/3061—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F17/30613—Indexing
    • G06F17/30619—Indexing indexing structures
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/0223—User address space allocation, e.g. contiguous or non contiguous base addressing
    • G06F12/023—Free address space management
    • G06F12/0253—Garbage collection, i.e. reclamation of unreferenced memory
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for programme control, e.g. control unit
    • G06F9/06—Arrangements for programme control, e.g. control unit using stored programme, i.e. using internal store of processing equipment to receive and retain programme
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/22—Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F2207/22—Indexing scheme relating to groups G06F7/22 - G06F7/36
    • G06F2207/226—Priority queue, i.e. 1 word in, 1 word out sorter; Output word, i.e. min or max of words in memory

Similar Documents

Publication Publication Date Title
Franceschini et al. An in-place sorting with O (n log n) comparisons and O (n) moves
Arge et al. Cache-oblivious priority queue and graph algorithm applications
Bender et al. Cache-oblivious B-trees
Demaine Cache-oblivious algorithms and data structures
US5487164A (en) Distribution-based replacement selection sorting system
Chazelle The soft heap: an approximate priority queue with optimal error rate
Vöcking How asymmetry helps load balancing
Thorup Integer priority queues with decrease key in constant time and the single source shortest paths problem
Bercken et al. An evaluation of generic bulk loading techniques
Bingmann et al. Engineering parallel string sorting
Arge et al. Cache-oblivious data structures
AU2004225060B2 (en) A computer implemented compact 0-complete tree dynamic storage structure and method of processing stored data
Tarjan et al. Zip trees
Arge et al. An optimal cache-oblivious priority queue and its application to graph algorithms
Arge et al. Cache-oblivious data structures
Kaporis et al. Improved bounds for finger search on a RAM
Edelkamp et al. The weak-heap data structure: Variants and applications
Edelkamp et al. Optimizing binary heaps
Breen et al. An evaluation of priority queues for mathematical morphology
Matias et al. Dynamic generation of discrete random variates
Arge et al. External memory algorithms for diameter and all-pairs shortest-paths on sparse graphs
Pagh Basic external memory data structures
Aspnes et al. Depth of a random binary search tree with concurrent insertions
Geffert et al. In-place sorting
Franceschini Sorting stably, in place, with O (n log n) comparisons and O (n) moves