MergeSort

#include <iostream>
#include <deque>
using namespace std;

// Print the contents of the list.
void PrintData(const deque<int>& arr)
{
for(unsigned i = 0; i < arr.size(); ++i)
cout << arr[i] << " ";

cout << endl;
}

// This function takes two sorted lists and merges them
deque<int> Merge(deque<int>& left, deque<int>& right)
{
deque<int> result;

// While there are still elements in one or both of the lists...

// If there are elements in both lists...
                      // Take the smaller of the two elements at the front of lists
                      // and add it to the result list

// Otherwise if the left list still has elements...
                     // Take the first element of the left list and add it to the result list

// Or if the right list still has elements...
                    // Take the first element of the right list and add it to the result list

        // Return the resulting list.
}

// This algorithm sorts a single list by splitting it in half and sorting those halves.
deque<int> MergeSort(const deque<int>& arr)
{
        // If the size of the list is less than or equal to 1, just return the list as is.

        // Else...

///////////////////////////////////
// Split the array down the middle 
// (or close to it if there are an 
// odd number of elements)
//////////////////////////////////

// Calculate the middle index

// Take elements from the first half and put them in the "left" list

// Take elements from the second half and put them in the "right" list

// Recursive calls to MergeSort to sort both halves

// Merge the sorted halves and return

}

int main()
{
deque<int> queue;
queue.push_back(1);
queue.push_back(5);
queue.push_back(2);
queue.push_back(4);
        queue.push_back(2);
queue.push_back(0);
PrintData(queue);
queue = MergeSort(queue);
PrintData(queue);

system("pause");
}
Comments