C++ implementation of merge sort

program-ape
, , , , , , 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/*
 * mergeSort.h
 *
 * Created on: Jan 4, 2012
 * Author: ycshao
 * If you find any bug, please contact me at ycshao0402@gmail.com.
 * Thank you!
 */

#ifndef MERGESORT_YCSHAO_H_
#define MERGESORT_YCSHAO_H_
#include <vector>
#include <iostream>

namespace ycshao
{
/* Sort the vector using default comparator. */
template <typename T>
void mergeSort(std::vector<T>* list);

/* Sort the vector using comparator function passed in. */
template <typename T, typename Comparator>
void mergeSort(std::vector<T>* list, Comparator comp);

namespace impl
{
/* Merge two sorted vector into a big sorted vector */
template <typename T, typename Comparator>
void merge(std::vector<T>& one, std::vector<T>& two, std::vector<T>* combination, Comparator comp);
} /* namespace impl */

/* Implementation below */
template <typename T>
void mergeSort(std::vector<T>* list)
{
	mergeSort(list, std::less<T>());
}

template <typename T, typename Comparator>
void mergeSort(std::vector<T>* list, Comparator comp)
{
	if (list->size() < 2)
	{
		return;
	}
	std::vector<T> one, two;
	for (unsigned int i = 0; i < list->size() / 2; ++i)
	{
		one.push_back((*list)[i]);
	}
	for (unsigned int i = list->size() / 2; i < list->size(); ++i)
	{
		two.push_back((*list)[i]);
	}
	mergeSort(&one, comp);
	mergeSort(&two, comp);
	impl::merge(one, two, list, comp);
}

namespace impl
{
template <typename T, typename Comparator>
void merge(std::vector<T>& one, std::vector<T>& two, std::vector<T>* combination, Comparator comp)
{
	combination->clear();
	combination->reserve(one.size() + two.size());
	unsigned int onePos = 0, twoPos = 0;
	while (onePos < one.size() && twoPos < two.size())
	{
		if (comp(one[onePos], two[twoPos]) == 1)
		{
			combination->push_back(one[onePos]);
			++onePos;
		}
		else
		{
			combination->push_back(two[twoPos]);
			++twoPos;
		}
	}
	while (onePos < one.size())
	{
		combination->push_back(one[onePos]);
		++onePos;
	}
	while (twoPos < two.size())
	{
		combination->push_back(two[twoPos]);
		++twoPos;
	}
}
} /* namespace impl */

} /*namespace ycshao*/

#endif /* MERGESORT_YSHAO_H_ */

In the code, I use a namespace impl to include functions that will be used only in this file.

C++0x has a much more elegant way to deal with it, I’ll research a little bit and post it.