Under de senaste åren har ett stort antal problem beaktats i externa minnesmodeller för beräkning, där komplexitetsmåttet är antalet datablock som flyttas mellan långsamt externt minne och snabbt internt minne (även kallade I/Os). I praktiken dominerar dock den interna minnestiden ofta den totala körtiden när I/O-effektivitet har uppnåtts. I detta dokument initierar vi en studie av algoritmer för grundläggande problem som samtidigt är I/O-effektiva och interna minnen effektiva i RAM-modellen för beräkning. För sortering är den konventionella visdomen att använda sammanslagning av basalgoritmer i externt minne, men vi beskriver hur detta leder till suboptimal RAM-prestanda. Genom att använda en uppdelningsbaserad algoritm i kombination med befintliga RAM-sorteringsmetoder får vi dock en sorteringsalgoritm som är både I/O- och RAM-modell effektiv. Dessutom designar vi en I/O- och RAM-effektiv prioriteringskö. Slutligen visar vi en sortering lägre gräns som i de flesta fall visar att våra resultat är optimala både när det gäller I/O och interna beräkningar.
En viktig del av några av de datastrukturer som presenteras i detta dokument är den prioriterade kön av Arge och Thorup REF, som samtidigt är effektiv i RAM och i externt minne.
RAM-Efficient External Memory Sorting
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}