Ваша версия теряла столько памяти, что время было бессмысленным.
Я уверен, что время было потрачено на перерасход памяти.
Перепишите его, чтобы использовать стандартные объекты C ++ для управления памятью std ::вектор и посмотрим, что получится.
Лично я бы все-таки ожидал, что Java-версия победит (просто).Поскольку JIT допускает оптимизацию для конкретной машины, и хотя C ++ может выполнять оптимизацию для конкретной машины, в целом он будет выполнять только общие оптимизации архитектуры (если вы не укажете точные флаги архитектуры).
- Примечание: не забудьтескомпилировать с включенными оптимизациями.
Просто очистить ваш C ++:
Я не пытался сделать хорошую сортировку слиянием (просто переписанную) в стиле C ++
void sort1(std::vector<double>& data)
{
if(data.size() > 1)
{
std::size_t centre = data.size() / 2;
std::size_t lftSize = centre;
std::size_t rhtSize = data.size() - lftSize;
// Why are we allocating new arrays here??
// Is the whole point of the merge sort to do it in place?
// I forget bbut I think you need to go look at a knuth book.
//
std::vector<double> lft(data.begin(), data.begin() + lftSize);
std::vector<double> rht(data.begin() + lftSize, data.end());
sort1(lft);
sort1(rht);
std::size_t dataPointer = 0;
std::size_t lftPointer = 0;
std::size_t rhtPointer = 0;
while((lftPointer < lftSize) && (rhtPointer < rhtSize))
{
data[dataPointer++] = (lft[lftPointer] <= rht[rhtPointer])
? lft[lftPointer++]
: rht[rhtPointer++];
}
std::copy(lft.begin() + lftPointer, lft.end(), &data[dataPointer]);
std::copy(rht.begin() + rhtPointer, rht.end(), &data[dataPointer]);
}
}
Думая о слиянии сортировки.Я бы попробовал это:
Я не проверял это, поэтому он может работать неправильно.Но это попытка не продолжать выделять огромные объемы памяти для выполнения сортировки.вместо этого он использует одну временную область и копирует результат обратно, когда сортировка завершена.
void mergeSort(double* begin, double* end, double* tmp)
{
if (end - begin <= 1)
{ return;
}
std::size_t size = end - begin;
double* middle = begin + (size / 2);
mergeSort(begin, middle, tmp);
mergeSort(middle, end, tmp);
double* lft = begin;
double* rht = middle;
double* dst = tmp;
while((lft < middle) && (rht < end))
{
*dst++ = (*lft < *rht)
? *lft++
: *rht++;
}
std::size_t count = dst - tmp;
memcpy(begin, tmp, sizeof(double) * count);
memcpy(begin + count, lft, sizeof(double) * (middle - lft));
memcpy(begin + count, rht, sizeof(double) * (end - rht));
}
void sort2(std::vector<double>& data)
{
double* left = &data[0];
double* right = &data[data.size()];
std::vector<double> tmp(data.size());
mergeSort(left,right, &tmp[0]);
}