CODEWITHSUNDEEP
c++algorithm
user656925
user656925

Reputation:

When does merge_sort beat quick_sort?

SO Posts

When to use merge sort and when to use quick sort?

Quick Sort Vs Merge Sort

Wikipedia

http://en.wikipedia.org/wiki/Merge_sort

http://en.wikipedia.org/wiki/Quicksort

quick_sort is suppose to have worst case O(n^2) but merge_sort is suppose to not have a worst case and always be O (n*log N). I thought that it was dependent upon the ordering of the data set - reverse order, forward order, or random, but when I a run test...quick_sort is always faster. The code I used is below:

/*
Needs a reszie function added
*/
#include "c_arclib.cpp"
template <class T> class dynamic_array
  {
  private:
    T* array;
    T* scratch;
  public:
    int size;
    dynamic_array(int sizein)
      {
      size=sizein;
      array = new T[size]();
      }
    void print_array()
      {
      for (int i = 0; i < size; i++) cout << array[i] << endl;
      }
    void merge_recurse(int left, int right)
      {
      if(right == left + 1)
        {
        return;
        }
      else
        {
        int i = 0;
        int length = right - left;
        int midpoint_distance = length/2;
        int l = left, r = left + midpoint_distance;
        merge_recurse(left, left + midpoint_distance);
        merge_recurse(left + midpoint_distance, right);
        for(i = 0; i < length; i++)
          {
          if((l < (left + midpoint_distance)) && (r == right || array[l] > array[r]))
            {
            scratch[i] = array[l];
            l++;
            }
          else
            {
            scratch[i] = array[r];
            r++;
            }
          }
        for(i = left; i < right; i++)
          {
          array[i] = scratch[i - left];
          }
        }
      }
    int merge_sort()
      {
      scratch = new T[size]();
      if(scratch != NULL)
        {
        merge_recurse(0, size);
        return 1;
        }
      else
        {
        return 0;
        }
      }
    void quick_recurse(int left, int right) 
      {  
      int l = left, r = right, tmp;
      int pivot = array[(left + right) / 2];
      while (l <= r)
        {
        while (array[l] < pivot)l++;
        while (array[r] > pivot)r--;
        if (l <= r) 
          {
          tmp = array[l];
          array[l] = array[r];
          array[r] = tmp;
          l++;
          r--;
          }
        }
      if (left < r)quick_recurse(left, r);
      if (l < right)quick_recurse(l, right);
      }  
    void quick_sort()
      {
      quick_recurse(0,size);
      }
    void rand_to_array()
      {
      srand(time(NULL));
      int* k;
      for (k = array; k != array + size; ++k)                                             
        { 
        *k=rand();                                      
        } 
      }
    void order_to_array()
      {
      int* k;
      int i = 0;
      for (k = array; k != array + size; ++k)                                             
        { 
        *k=i;
        ++i;        
        } 
      }
    void rorder_to_array()
      {
      int* k;
      int i = size;
      for (k = array; k != array + size; ++k)                                             
        { 
        *k=i;
        --i;        
        } 
      }
  };
int main()
  {
  dynamic_array<int> d1(1000000);
  d1.order_to_array();
  clock_t time_start=clock();
  d1.merge_sort(); 
  clock_t time_end=clock();
  double result = (double)(time_end - time_start) / CLOCKS_PER_SEC; 
  cout << result;
  }

Upvotes: 2

Views: 411

Answers (3)

Mark Ransom
Mark Ransom

Reputation: 308121

Merge sort works very well for data that won't fit into memory, because each pass is linear and can be read/written to disk. Quick sort isn't even an option in that case, although the two may be combined - quick sort blocks that fit into memory, and merge sort those blocks until done.

Upvotes: 1

Karl Knechtel
Karl Knechtel

Reputation: 61498

Consider the container type as well - mergesort will work much better with a linked list, because you can split the list into equal parts by just traversing it and assigning nodes to alternate sublists; rearranging things around a pivot for quicksort is considerably more involved.

Upvotes: 0

BrokenGlass
BrokenGlass

Reputation: 160852

Worst case for quick sort is when the pivot element is the largest or smallest element in the array on every recursion. In that case you will have to do n-1 recursions (one of the arrays you split always only has one element) which gives you an O(n2) overall.

You can reproduce the worst case for quick sort if you use an already sorted array and pick the first or last element as pivot element.

Upvotes: 2

Related Questions