Sorting Algorithm - Memory Usage Patterns and Index Sorting

Memory Usage Patterns and Index Sorting

When the size of the array to be sorted approaches or exceeds the available primary memory, so that (much slower) disk or swap space must be employed, the memory usage pattern of a sorting algorithm becomes important, and an algorithm that might have been fairly efficient when the array fit easily in RAM may become impractical. In this scenario, the total number of comparisons becomes (relatively) less important, and the number of times sections of memory must be copied or swapped to and from the disk can dominate the performance characteristics of an algorithm. Thus, the number of passes and the localization of comparisons can be more important than the raw number of comparisons, since comparisons of nearby elements to one another happen at system bus speed (or, with caching, even at CPU speed), which, compared to disk speed, is virtually instantaneous.

For example, the popular recursive quicksort algorithm provides quite reasonable performance with adequate RAM, but due to the recursive way that it copies portions of the array it becomes much less practical when the array does not fit in RAM, because it may cause a number of slow copy or move operations to and from disk. In that scenario, another algorithm may be preferable even if it requires more total comparisons.

One way to work around this problem, which works well when complex records (such as in a relational database) are being sorted by a relatively small key field, is to create an index into the array and then sort the index, rather than the entire array. (A sorted version of the entire array can then be produced with one pass, reading from the index, but often even that is unnecessary, as having the sorted index is adequate.) Because the index is much smaller than the entire array, it may fit easily in memory where the entire array would not, effectively eliminating the disk-swapping problem. This procedure is sometimes called "tag sort".

Another technique for overcoming the memory-size problem is to combine two algorithms in a way that takes advantages of the strength of each to improve overall performance. For instance, the array might be subdivided into chunks of a size that will fit easily in RAM (say, a few thousand elements), the chunks sorted using an efficient algorithm (such as quicksort or heapsort), and the results merged as per mergesort. This is less efficient than just doing mergesort in the first place, but it requires less physical RAM (to be practical) than a full quicksort on the whole array.

Techniques can also be combined. For sorting very large sets of data that vastly exceed system memory, even the index may need to be sorted using an algorithm or combination of algorithms designed to perform reasonably with virtual memory, i.e., to reduce the amount of swapping required.

Some other sorting algorithms also i.e. New friends sort algorithm, Relative split and concatenate sort etc

Read more about this topic:  Sorting Algorithm

Famous quotes containing the words memory, usage, patterns and/or index:

    It must be a peace without victory.... Victory would mean peace forced upon the losers, a victor’s terms imposed upon the vanquished. It would be accepted in humiliation, under duress, at an intolerable sacrifice, and would leave a sting, a resentment, a bitter memory upon which the terms of peace would rest, not permanently, but only as upon quicksand.
    Woodrow Wilson (1856–1924)

    I am using it [the word ‘perceive’] here in such a way that to say of an object that it is perceived does not entail saying that it exists in any sense at all. And this is a perfectly correct and familiar usage of the word.
    —A.J. (Alfred Jules)

    I’ve begun to appreciate the generational patterns that ripple out from our lives like stones dropped in water, pulsing outward even after we are gone. Although we have but one childhood, we relive it first through our children’s and then our grandchildren’s eyes.
    Anne Cassidy (20th century)

    Exile as a mode of genius no longer exists; in place of Joyce we have the fragments of work appearing in Index on Censorship.
    Nadine Gordimer (b. 1923)