Merge Sorting with STL

[Slater]

Alright, I had this project to compare the time it takes to sort large ammounts of data using different sorting algorithms (selection, bubble, radix, etc). I, for the most part, got all the algorithms down... except for Merge sorting, which is weird because I've done it before with ease.


So, I'm wondering if someone can help me out here. The skeleton of the program is as follows...

Code: Select all

#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <cstdlib>
#include <time>
using namespace std;

typedef int ItemType;
typedef list<ItemType> ADT; //short for Abstract Data Type

blah blah blah code here

class Sort
    {
    public:
        blah blah blah public functions here
   
    protected:
        void mergeSort(void);
   
    private:
        ADT items;
        void _merge(ADT::iterator first, ADT::iterator mid, ADT::iterator last);
        void _mergeSort(ADT::iterator first, ADT::iterator last);
        (insert more private members here)
    }


Ok, all this is defined in the project specifications. Furthermore, the function mergeSort(void) is implemented (not allowed to change this).

Code: Select all

void Sort::mergeSort(void);
    {
    _mergeSort(items.begin(), items.end());
    }


yeah, real flippin hard function there.

Anyhow, I'll draw the attention back to the declaration of typedef ADT. In this example, I made it of the STL list type. However, the doccumentation says that this merge sort should work if ADT is changed to deque or vector.

I honestly have no clue how to go about writing these functions. Could someone give me some pointers?

Edit: Kewl, that post somehow broke the forum tables... --;

[Warrior4Christ]

Merge sort works recursively - if I remember correctly, it goes a bit like this "pseudocode" (where list1[a,b] means a list containing the elements in list1 from index a to index b):

Code: Select all

list _mergeSort(list) {
   if(list.size!=1){
      list1= _mergeSort(list[first,(first+last)/2]);
      list2= _mergeSort(list[(first+last)/2,last]);
      mergedlist= _merge(list1,list2);
      return mergedList;
   }else{
      return list;
   }
}

list _merge(list1,list2) {
   list result;
   do{
      if(list1[0]<list2[0]){
         result.add(list1[0]);
         list1.remove(0);
      }else{
         result.add(list2[0]);
         list2.remove(0);
      }
   }while(list1.size>0 && list2.size>0);
   if(list1.size>0){
      result.add(list1[0,list1.size()]);
   }
   if(list2.size>0){
      result.add(list2[0,list2.size()]);
   }
   return result;
}

merge() merges two sorted lists into one sorted list, and mergeSort splits the unsorted list into two lists to mergeSort.

But of course, yours has different parameter types, and uses iterators (huh?) and does not return a list type. So you'll have to translate it to fit your function declaration things.

[Slater]

right... Like I said, it's really really easy with vectors and deques, but with lists...

Lists aren't random access. Can't just say "oh, the middle of the list is there."

after checking your pseudocode, I think I got a few new ideas for how to maybe find the middle... but after that, it's still kinda funky...

Man, what happened to the good old days of arrays being good enough...

[Warrior4Christ]

How do lists work in C++ again? I don't really have extensive experience with STL lists... or the STL in general.

[Icarus]

Basically, lists are the node value and a pointer to the next node. You can add some other things, like counters, indexes, cursors, and so on.

If I was doing merge sort with lists, I'd keep a couple of cursors handy, one at the head of the original list, and another halfway through, Then I'd just create a temporary list containing the first half, and pass those two to the algorithm.

$0.02 tendered. Keep the change.