Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 2 of 2

Thread: heap sort vs merge sort

  1. #1
    Join Date
    May 2011
    My Mood
    Thanked 0 Times in 0 Posts

    Default heap sort vs merge sort

    I found this quoted from WIkipedia interesting:
    "Like quicksort, merge sort on arrays has considerably better data cache performance, often outperforming heapsort on modern desktop computers because merge sort frequently accesses contiguous memory locations (good locality of reference); heapsort references are spread throughout the heap."

    So accessing memory locations adjacent to one another will result in caching these locations on modern machines? Can someone help explain a little better, I am new to memory management, I'll look up to...

  2. #2
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Thanked 619 Times in 561 Posts
    Blog Entries

    Default Re: heap sort vs merge sort

    The idea is that your CPU has internal cache memory which is significantly faster than your system memory. However, it's usually quite small (my CPU has an L3 cache of 3 MB compared to a system memory of 8 GB). There are multiple cache levels, with each having a speed/size trade-off. At the very end you have registers which are the fastest, but you only get a handful of registers.

    If you can coalesce as many read/writes as possible so they operate on data already in the cache, you'll have better performance than if you had to constantly retrieve data from main memory. Every time you have to read/write data from main memory is a cache miss. The better you can coalesce read/writes the better your memory locality and thus the better your chances of having your code take advantage of cache memory.

    There are a many different strategies for improving memory locality, not just trying to access data sequentially. For example, I could divide a large array into tiles which fit into my cache then do as any operations I wanted on that tile before moving to the next tile. If you look at the way mergesort works, this is basically what it does: it divides the data in half, and recursively sorts each half. At a certain point the entire dataset will fit into cache memory and can be sorted very fast.

    Actual performance benefits of memory locality depends from case to case, I've seen cases where speedups have been an order of magnitude better and others which are only marginally better, or perform worse due to added complexity. Memory locality and exploiting the cache aren't usually the first place I go looking for performance benefits. A better bounded algorithm usually provides significantly better performance than any amount of micro optimization can provide. I say usually because there are cases where better bounded algorithms sometimes have extremely large factors which make them perform poorly in practice.

Similar Threads

  1. How to call a C sort function to sort a Java Array.
    By Dwere13 in forum Java Native Interface
    Replies: 22
    Last Post: July 12th, 2012, 04:44 PM
  2. [SOLVED] displaying every 1000 comparisons in merge sort
    By mia_tech in forum What's Wrong With My Code?
    Replies: 6
    Last Post: May 27th, 2012, 07:26 PM
  3. [SOLVED] counting number of comparisons in merge sort
    By mia_tech in forum What's Wrong With My Code?
    Replies: 9
    Last Post: May 26th, 2012, 11:54 PM
  4. Replies: 0
    Last Post: November 6th, 2011, 03:55 PM
  5. Merge sort not sorting at all despite copying it exact from book.
    By javapenguin in forum Other Programming Languages
    Replies: 1
    Last Post: November 1st, 2011, 04:31 PM