( *logno( *lognfair yes heapsort ( *logno( *lognfair no table summarizes the running time for various sorting algorithms the column labeled comparison attempts to estimate the minor speed differences between algorithms with the same average big times (there' no entry for shellsort because there are no other algorithms with the same big performance external storage in the previous discussion we assumed that data was stored in main memory howeveramounts of data too large to store in memory must be stored in external storagewhich generally means disk files we discussed external storage in the second parts of tables and external storage,and "hash tables we assumed that data is stored in disk file in fixed-size units called blockseach of which holds number of records ( record in disk file holds the same sort of data as an object in main memory like an objecta record has key value used to access it we also assumed that reading and writing operations always involve single blockand these read and write operations are far more time-consuming than any processing of data in main memory thus for fast operation the number of disk accesses must be minimized sequential storage the simplest approach is to store records randomly and read them sequentially when searching for one with particular key new records can simply be inserted at the end of the file deleted records can be marked as deletedor records can be shifted down (as in an arrayto fill in the gap on the averagesearching and deletion will involve reading half the blocksso sequential storage is not very fastoperating in (ntime stillit might be satisfactory for small number of records indexed files speed is increased dramatically when indexed files are used in this scheme an index of keys and corresponding block numbers is kept in main memory to access record with specified keythe index is consulted it supplies the block number for the keyand only one block needs to be readtaking ( time several indices with different kinds of keys can be used (one for last namesone for social security numbersand so onthis scheme works well until the index becomes too large to fit in memory typically the index files are themselves stored on disk and read into memory as needed the disadvantage of indexed files is that at some point the index must be created this probably involves reading through the file sequentiallyso creating the index is slow alsothe index will need to be updated when items are added to the file -trees