data structures using comparison of sorting algorithms table comparison of algorithms algorithm average case ( worst case ( selection sort ( ko( ( ko( insertion sort ( ( shell sort ( log nmerge sort ( log no( log nheap sort ( log nquick sort ( log no( log no( bubble sort bucket sort table compares the average-case and worst-case time complexities of different sorting algorithms discussed so far external sorting external sorting is sorting technique that can handle massive amounts of data it is usually applied when the data being sorted does not fit into the main memory (ramandthereforea slower memory (usually magnetic disk or even magnetic tapeneeds to be used we will explain the concept of external sorting using an example discussed below example let us consider we need to sort mb of data using only mb of ram the steps for sorting are given below step read mb of the data in ram and sort this data using any conventional sorting algorithm like quick sort step write the sorted data back to the magnetic disk step repeat steps and until all the data (in mb chunksis sorted all these seven chunks that are sorted need to be merged into one single output file step read the first mb of each of the sorted chunks and call them input buffers sonow we have mb of data in the ram allocate the remaining ram for output buffer step perform seven-way merging and store the result in the output buffer if at any point of timethe output buffer becomes fullthen write its contents to the final sorted file howeverif any of the input buffers gets emptyfill it with the next mb of its associated mb sorted chunk or else mark the input buffer (sorted chunkas exhausted if it does not has any more left with it make sure that this chunk is not used for further merging of data the external merge sorting can be visualized as given in fig / buffers in ram disk disk input input output input figure external merge sorting generalized external merge sort algorithm from the example abovewe can now present generalized merge sort algorithm for external sorting if the amount of data to be sorted exceeds the available memory by factor of kthen chunks (also known as run listsof data are created these chunks are sorted and then -way merge is performed if the amount of ram available is given as xthen there will be input buffers and output buffer