Implemented merge sort.

2 files changed, 108 insertions, 0 deletions

diff --git a/merge-sort.cpp b/merge-sort.cpp
new file mode 100644
index 0000000..e7647a0
--- /dev/null
+++ b/merge-sort.cpp
@@ -0,0 +1,107 @@
+
+#include <cstdlib>
+#include <cstring>
+#include <iostream>
+#include <deque>
+
+using namespace std;
+
+typedef std::deque<int> list_t;
+
+void merge(list_t& lst, list_t left, list_t right)
+{
+    list_t res;
+    while (!left.empty() || !right.empty())
+    {
+        if (!left.empty() && !right.empty())
+        {
+            if (left[0] <= right[0])
+            {
+                res.push_back(left[0]);
+                left.pop_front();
+            }
+            else
+            {
+                res.push_back(right[0]);
+                right.pop_front();
+            }
+        }
+        else if (!left.empty())
+        {
+            res.push_back(left[0]);
+            left.pop_front();
+        }
+        else if (!right.empty())
+        {
+            res.push_back(right[0]);
+            right.pop_front();
+        }
+    }
+
+    res.swap(lst);
+}
+
+void merge_sort(list_t& lst)
+{
+    size_t n = lst.size();
+    if (n <= 1)
+        return;
+
+    list_t left, right;
+    size_t mpos = n / 2;
+    for (size_t i = 0; i < n; ++i)
+    {
+        if (i < mpos)
+            left.push_back(lst[i]);
+        else
+            right.push_back(lst[i]);
+    }
+
+    merge_sort(left);
+    merge_sort(right);
+    merge(lst, left, right);
+}
+
+void print_list(const list_t& lst, const char* caption)
+{
+    cout << caption << ": ";
+    for (list_t::const_iterator i = lst.begin(), ie = lst.end(); i != ie; ++i)
+        cout << *i << " ";
+    cout << endl;
+}
+
+int main(int argc, char** argv)
+{
+    if (argc < 2)
+    {
+        cout << "needs at least one argument" << endl;
+        return EXIT_FAILURE;
+    }
+
+    const char* p = argv[1];
+    const char* pend = p + strlen(p);
+    char* endptr = NULL;
+    long list_size = strtol(p, &endptr, 10);
+    if (endptr != pend)
+    {
+        cout << "invalid number: " << p << endl;
+        return EXIT_FAILURE;
+    }
+
+    cout << "list size: " << list_size << endl;
+
+    list_t lst;
+    for (int i = 0; i < list_size; ++i)
+    {
+        double val = rand();
+        val /= RAND_MAX;
+        val *= 50;
+        lst.push_back(val);
+    }
+
+    print_list(lst, "original");
+    merge_sort(lst);
+    print_list(lst, "sorted");
+
+    return EXIT_SUCCESS;
+}
diff --git a/slickedit/algorithms.vpj b/slickedit/algorithms.vpj
index 214defe..4c86232 100644
--- a/slickedit/algorithms.vpj
+++ b/slickedit/algorithms.vpj
@@ -130,6 +130,7 @@
 		<Folder
 			Name="Source Files"
 			Filters="*.c;*.C;*.cc;*.cpp;*.cp;*.cxx;*.c++;*.prg;*.pas;*.dpr;*.asm;*.s;*.bas;*.java;*.cs;*.sc;*.e;*.cob;*.html;*.rc;*.tcl;*.py;*.pl;*.d">
+			<F N="../merge-sort.cpp"/>
 			<F N="../reverse-string.cpp"/>
 			<F N="../tree.cpp"/>
 			<F N="../unique-char.cpp"/>