A typical implementation of quick sort works on quick sorting subarray and comparison is done in a linear manner that is a[i] is compared with pivot and then a[i+1] and so on. Virtual memory systems employ some sort of caching. Caching works on the principle of spatial locality of reference. That said, once a comparison begins, after a miss in the cache, cache is fetched for the miss(a[i]) as well as for next few more memory cells (a[i+1], a[i+2], etc). This ensures that next 'few'(typically 3-5) iteration of the loop will be a cache hit, there by speeding up the algorithm.
-Moheed "I am who I am, no matter where I am or who I am with." * * On Sun, Jan 29, 2012 at 12:38 AM, karthikeya s <[email protected]>wrote: > How QuickSort is good in Virtual Memory Enviroment ? > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
