Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Why insertion sort works better than quick-sort for small data?

  1. Jun 19, 2013 #1
    I have seen in books that when number of elements is small ~ 30-40 insertion sort is recommended. Why is that? The worst case of insertion sort is n2 whereas for quick-sort it is nlogn.

    nlogn beats n2 for all values of n isn't it? Then why?
     
  2. jcsd
  3. Jun 19, 2013 #2

    jtbell

    User Avatar

    Staff: Mentor

    Each step of quicksort normally requires more "work" than a step of insertion sort. Compare 10000 n log n with 10 n2. Of course, this is an exaggeration, but it illustrates the basic idea.
     
  4. Jun 20, 2013 #3
    Merge sort is much easier for me so lets talk compare merge-sort with insertions sort.
    In worst case insertion sort will be 1 + 2 + 3 + ... + n which is n.(n+1) / 2 iterations/steps.
    There is not worst case in merge sort. Each step (that is dividing the array by two) takes n iterations (that is merging). This happens logn or logn + 1 times. Thus total iterations/steps is n.logn or n.logn + n

    Where does the constant in front comes from?
     
  5. Jun 20, 2013 #4

    rcgldr

    User Avatar
    Homework Helper

    Using a bottom up merge sort is easier to explain. In a top down merge sort, no merging takes place until sub-array's of size 1 are produced by recursively dividing the array by 2 (or creating a tree of indexes on the stack).

    The initial condition of a merge sort considers an array of size n as n arrays of size 1 (an array of size 1 can be considered sorted) and the first pass merges those n arrays of size 1 into a secondary buffer producing n/2 sorted arrays of size 2. The next pass merges the n/2 sorted arrays of size 2 back into the primary buffer producing n/4 sorted arrays of size 4. This merge process is repeated until there is 1 sorted array. The number of elements moved on each pass is n, and the number of passes is log2(n), so the number of moves is n log2(n). The worst case number of compares is n log2(n) - n + 1. This is explained next:

    On the first pass each pair of arrays of size 1 are merged taking 1 compare, so that's n/2 compares. On the second pass, the worst case number of compares for each pair of arrays of size 2 is 3, so that's 3n/4 compares. For the third pass, 7n/8. For the final log2(n) pass, each pair of arrays of size n/2 are merged taking n-1 compares in the worst case, for a total of (n-1) n / n = n - 1. To calculate the sum, subtract 1x the number of compares from 2x the number of compares:

    Code (Text):

      2x # compares = 1n/1 + 3n/2 + 7n/4 + ...
    - 1x # compares =        1n/2 + 3n/4 + ... + (n-1)
    ------------------------------------------------
      1x # compares =    n +    n +    n + ... - (n-1) = n log2(n) - n + 1
     
     
    Last edited: Jun 20, 2013
  6. Jun 20, 2013 #5
    Thanks for the explanation.
    Anyways where do the constants 10000 and 10 come up? As explained above the number of steps/comparisons is n log2n ... no big constants in it
     
  7. Jun 20, 2013 #6

    rcgldr

    User Avatar
    Homework Helper

    I updated my previous post to explain how the worst case number of compares are calclated.

    That was an exagerration. The issue is the number of temporary variables, like indexes, and size of array, and how often they have to be updated in order to implement a sort algorithm. So the overhead per comparason, swap, or move may be higher for the "better" algorithms, making them slower if the number of elements in an array is very small.
     
  8. Jun 20, 2013 #7
    Yeah I knew they were an exaggeration but couldn't see how any constants could rise. I totally forgot about overhead time taken to divide the array into two, calling other functions, swapping etc.
    I was just looking at the comparisons!
    Anyways thank you for clearing the doubt
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Why insertion sort works better than quick-sort for small data?
  1. Sorting revisited. (Replies: 17)

  2. Selection sort? (Replies: 2)

  3. Sorting algorithm? (Replies: 2)

  4. Perfect sort (Replies: 2)

  5. Merge sort (Replies: 1)

Loading...