Wednesday 9 October 2013

Merge Sort without Recursion.

MathJax TeX Test Page
Well, I needed a sorting algorithm in C++, so I decided to write my own. Merge sort is quick, O(nlogn), and stable. Recursion is also slow so I decided to write it without recursion:


  // array to be sorted
  int array[] = {12,4,10,2,3,2,8,7,-1,-4,14,8,9,2,11};
  unsigned int len = 15;
  // allocate memory for temporarly saved values
  std::vector tempValues;
  tempValues.resize(len);
  // start sorting 2 elements each time, then merge them with the two next to them etc
  for(int step=2; step/2 < len; step*=2)
  {
     for(unsigned int i=0; i < len; i+=step)
     {
        int endOfT2 = i+step;
        if(i+ step/2 >= len)
        {
           continue;
        }
        else if (i+step >= len)
        {
           endOfT2 = len;
        }
        // both sets have step/2 items.
        // t1 points to the first set of values
        int t1 = i;
        // t2 points to the second set of values
        int t2 = i+step/2;
        // here we save all the values that have been overridden from the first set
        unsigned int tempIndex=0;
        while(t1 < i+step/2 && t2 < endOfT2)
        {
           if(array[t1]>array[t2])
           {
              tempValues[tempIndex]=array[t1];
              t1++;
           }
           else
           {
              tempValues[tempIndex]=array[t2];
              t2++;
           }
           tempIndex++;
        }
        while(t1 < i+step/2)
        {
           tempValues[tempIndex]=array[t1];
           t1++;
           tempIndex++;
        }
        // write values back to the array
        for(unsigned int t=0; t < tempIndex; ++t)
        {
            array[i+t]=tempValues[t];
        }
     }
  }

  // print the sorted array
  for(unsigned int i=0; i < len; ++i)
  {
      std::cout << " " << array[i];
  }
  std::cout << "\n";

No comments:

Post a Comment