notes thereforethe probability follows the binomial distributionwhich has meane[ninp variancevar[ninp( / for any random variablewe have [ nivar[nie [ni / th( putting this value in equation above(do some tweakingand we have expected time for insertion_sorto(nnow back to our original problem in the above bucket sort algorithmwe observe ( [time to insert elements in array [time to go through auxiliary array [ - (sort by insertion_sorto( ( - (no(nthereforethe entire bucket sort algorithm runs in linear expected time task discuss bubble sort with suitable example external sorting external sorting refers to the sorting of file that is on disk (or tapeinternal sorting refers to the sorting of an array of data that is in ram the main concern with external sorting is to minimize disk access since reading disk block takes about million times longer than accessing an item in ram (according to shaffer see the reference at the end of this documentperhaps the simplest form of external sorting is to use fast internal sort with good locality of reference (which means that it tends to reference nearby itemsnot widely scattered itemsand hope that your operating system' virtual memory can handle it (quicksort is one sort algorithm that is generally very fast and has good locality of reference if the file is too hugehowevereven virtual memory might be unable to fit it alsothe performance may not be too great due to the large amount of time it takes to access data on disk methods most external sort routines are based on mergesort they typically break large data file into number of shortersorted "runsthese can be produced by repeatedly reading section of the data file into ramsorting it with ordinary quicksortand writing the sorted data to disk after the sorted runs have been generateda merge algorithm is used to combine sorted files into longer sorted files the simplest scheme is to use -way mergemerge sorted files into one sorted filethen merge moreand so on until there is just one large sorted file better scheme is multiway merge algorithmit might merge perhaps shorter runs together lovely professional university