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 <karthikeya.a...@gmail.com>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 algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
