Обновление моего оригинального ответа ниже с помощью более общего кода с использованием итераторов коллекций, а не только векторов.
// merge a sort collection
template<typename CollectionT>
void mergeCollection(CollectionT & collection, CollectionT & tmpCollection,
typename CollectionT::iterator first, typename CollectionT::iterator mid,
typename CollectionT::iterator last) {
using IteratorType = typename CollectionT::iterator;
IteratorType left = first;
IteratorType leftEnd = mid;
IteratorType temp = tmpCollection.begin();
auto const distance = std::distance(collection.begin(), first);
std::advance(temp, distance);
IteratorType right = mid;
IteratorType rightEnd = last;
// finger matching algo left and right
while (left != leftEnd && right != rightEnd) {
// this first if block here for equals is what does your duplicate removal magic
if (*left == *right) {
*temp++ = *left++;
*temp++ = *right++; // ++right for non-duplicate
}
else if (*left < *right) {
*temp++ = *left++;
}
else {
*temp++ = *right++;
}
}
// copy rest of left
while (left != leftEnd) {
*temp++ = *left++;
}
// copy rest of right
while (right != rightEnd) {
*temp++ = *right++;
}
collection = tmpCollection;
}
template<typename CollectionT>
void mergeSortCollection(CollectionT & collection, CollectionT & tmpCollection, typename CollectionT::iterator first, typename CollectionT::iterator last) {
auto const distance = std::distance(first, last);
if(distance > 1) {
// get mid iterator
auto mid = first;
std::advance(mid, distance / 2);
mergeSortCollection(collection, tmpCollection, first, mid);
mergeSortCollection(collection, tmpCollection, mid, last);
mergeCollection(collection, tmpCollection, first, mid, last);
}
}
template<typename CollectionT>
void mergeSortCollection(CollectionT & collection) {
CollectionT tmpCollection {collection};
mergeSortCollection(collection, tmpCollection, collection.begin(), collection.end());
}
}
тестовый код:
namespace {
template<typename It>
auto printCollection =
[](std::ostream& out, It const begin, It const end, std::string const & message = "") {
using ValueType = typename std::iterator_traits<It>::value_type;
out << message;
std::copy(begin, end, std::ostream_iterator<ValueType>(out, ", "));
out << std::endl;
};
}
TEST(Sort, MergeSortCollectionVector) {
std::vector<int32_t> before = { 83, 86, 77, 15, 93, 35, 86, 92, 49, 21 };
std::vector<int32_t> original = before;
std::vector<int32_t> after = { 15, 21, 35, 49, 77, 83, 86, 86, 92, 93 };
printCollection<decltype(before.begin())>(std::cout, before.begin(), before.end(), "BEFORE sort: ");
mergeSortCollection(before);
printCollection<decltype(before.begin())>(std::cout, before.begin(), before.end(), "AFTER sort: ");
EXPECT_EQ(after, before);
EXPECT_NE(original, before);
}
TEST(Sort, MergeSortCollectionList) {
std::list<int32_t> before = { 83, 86, 77, 15, 93, 35, 86, 92, 49, 21 };
std::list<int32_t> original = before;
std::list<int32_t> after = { 15, 21, 35, 49, 77, 83, 86, 86, 92, 93 };
printCollection<decltype(before.begin())>(std::cout, before.begin(), before.end(), "BEFORE sort: ");
mergeSortCollection(before);
printCollection<decltype(before.begin())>(std::cout, before.begin(), before.end(), "AFTER sort: ");
EXPECT_EQ(after, before);
EXPECT_NE(original, before);
}
Как уже отмечали другие, вам потребуется некоторая модификация процесса merge, чтобы соответствовать вашим потребностям. Ниже приведена модифицированная merge() функция для вашей справки (оригинал здесь )
function merge(left,right)
var list result
while length(left) > 0 and length(right) > 0
if first(left) < first(right) // <--- change from <= to <
append first(left) to result
left = rest(left)
else if first(left) > first(right)
append first(right) to result
right = rest(right)
else // <----- added case to remove duplicated items
append first(right) to result
left = rest(left)
right = rest(right)
end
end while
if length(left) > 0
append left to result
else
append right to result
return result