Natural Merge Sort
A natural merge sort is similar to a bottom up merge sort except that any naturally occurring runs (sorted sequences) in the input are exploited. In the bottom up merge sort, the starting point assumes each run is one item long. In practice, random input data will have many short runs that just happen to be sorted. In the typical case, the natural merge sort may not need as many passes because there are fewer runs to merge. For example, in the best case, the input is already sorted (i.e., is one run), so the natural merge sort need only make one pass through the data.
Read more about this topic: Merge Sort
Famous quotes containing the words natural, merge and/or sort:
“The superstition respecting power and office is going to the ground. The stream of human affairs flows its own way, and is very little affected by the activity of legislators. What great masses of men wish done, will be done; and they do not wish it for a freak, but because it is their state and natural end.”
—Ralph Waldo Emerson (1803–1882)
“In good company, the individuals merge their egotism into a social soul exactly co-extensive with the several consciousnesses there present.”
—Ralph Waldo Emerson (1803–1882)
“Would you convey my compliments to the purist who reads your proofs and tell him or her that I write in a sort of broken-down patois which is something like the way a Swiss waiter talks, and that when I split an infinitive, God damn it, I split it so it will stay split, and when I interrupt the velvety smoothness of my more or less literate syntax with a few sudden words of bar- room vernacular, that is done with the eyes wide open and the mind relaxed but attentive.”
—Raymond Chandler (1888–1959)