Improve Run GenerationInternal Quick SortAlternative Internal Sort SchemeSteady State OperationNew StrategySlide 6InitializeSlide 8Slide 9Slide 10Slide 11Slide 12Generate Run 1Slide 14Slide 15Slide 16Slide 17Continue With Run 1Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Merging Runs Of Different LengthImprove Run Generation•Overlap input,output, and internal CPU work.•Reduce the number of runs (equivalently, increase average run length).DISKMEMORYDISKInternal Quick Sort6 2 8 5 11 10 4 1 9 7 3Use 6 as the pivot (median of 3).Input first, middle, and last blocks first.In-place partitioning.Input blocks from the ends toward the middle.Sort left and right groups recursively.Can begin output as soon as left most block is ready.4 2 3 5 1 6 10 11 9 7 8Alternative Internal Sort SchemeDISKDISKB1 B2 B3Partition into 3 areas, each may be more than 1 block in size.Steady State OperationRead from diskWrite to diskRun generation•Synchronization is done when the current input area gets full (the current output area will be empty at this time).DISKMEMORYDISKNew Strategy•Use 2 input and 2 output buffers.•Rest of memory is used for a min loser tree.Input 1Input 0Output 0 Output 1Loser Tree• Actually, 3 buffers adequate.Steady State OperationRead from diskWrite to diskRun generation•Synchronization is done when the active input buffer gets empty (the active output buffer will be full at this time).4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8438O0 O1I0I1Initialize4 3 6 8 1 5 7 3 2 6 9 4 5 2 5 84683517InitializeO0 O1I0I14 3 6 8 1 5 7 3 2 6 9 4 5 2 5 846835371629InitializeO0 O1I0I14 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8468353725281649InitializeO0 O1I0I14 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8468353725581649InitializeO0 O1I0I14 3 6 8 1 5 7 3 2 6 9 4 5 2 5 8468353725582649InitializeO0 O1I0I1Generate Run 114 3 6 8 5 7 3 2 6 9 4 5 2 5 8468353725582649O0 O1I0I1354Generate Run 14 3 6 8 5 7 3 2 6 9 4 5 2 5 8468353725582649O0 O1I0I13541335O023Generate Run 14 3 6 8 5 7 3 6 9 4 5 2 5 8468353725583649O1I0I135415445O023Generate Run 14 3 6 8 5 7 3 6 9 4 525 8468353725583649O1I0I13541545O0234 3 6 8 5 7 3 6 9 4 525 8468353725583649O1I0I115441925O0234 3 6 8 5 7 3 6 9 4 525 8468353745583649O1I0I11544192Continue With Run 1O1345O024 3 6 8 5 7 3 6 9 4 525 8468353745584649I0I1151192Continue With Run 1151O1345O024 3 6 8 5 736 9 4 525 8468353745584649I0I1151192Continue With Run 15995791O1345O02436 8 5 736 9 4 525 8468353745584649I0I1151192Continue With Run 15957291O1345O0436 8 5 736 9 4 5 5 8468353745584649I0I1516135957291O1345O0436 8 5 736 9 4 5 5 8468353745584649I0I15161359572Continue With Run 122 91O1345O0436 8 5 736 9 4 5 5 8468353745584649I0I1516135957Continue With Run 126652 91O1345O0436 8 5 736 945 5 8468353745584649I0I1516135957Continue With Run 126651195•Let k be number of external nodes in loser tree.•Run size >= k.•Sorted input => 1 run.•Reverse of sorted input => n/k runs.•Average run size is ~2k.•Memory capacity = m records.•Run size using fill memory, sort, and output run scheme = m.•Use loser tree scheme.Assume block size is b records.Need memory for 4 buffers (4b records).Loser tree k = m – 4b.Average run size = 2k = 2(m – 4b).2k >= m when m >= 8b.•Assume b = 100.m 600 1000 5000 10000k 200 600 4600 96002k 400 1200 9200 19200•Total internal processing time using fill memory, sort, and output run scheme = O((n/m) m log m) = O(n log m).•Total internal processing time using loser tree = O(n log k).•Loser tree scheme generates runs that differ in their lengths.4 3 6 9Merging Runs Of Different Length4 3697