我似乎无法弄清楚为什么我的合并排序太慢了

I have been looking through all of the threads here and couldn't seem to find a solution that worked. The sort works, but it's incredibly slow compared to what it should be. Here is the code (i'm working out of a header file):

我一直在查看这里的所有线程,似乎无法找到有效的解决方案。排序有效,但与应有的相比,速度非常慢。这是代码(我正在使用头文件):

#pragma once
#ifndef DataGen_h
#define DataGen_h

#include "RandomSupport.h"

void merge(long list[], long start, long mid, long end) { 
    long i = start; 
    long j = mid + 1; 
    while (j <= end && i <= mid) { 
        if (list[i] < list[j]) {
            i++; 
        } 
        else { 
            long temp = list[j]; 
            for (long k = j; k > i; k--) {
            list[k] = list[k - 1]; 
            }
            list[i] = temp; 
            mid++; 
            i++; 
            j++; 
        } 
    } 
}

void merge_sort(long list[], long startIndex, long endIndex)
{
    if (startIndex >= endIndex){
        return;
    }

    long midIndex = (startIndex + endIndex) / 2;
    merge_sort(list , startIndex, midIndex);
    merge_sort(list, midIndex + 1, endIndex);
    merge(list, startIndex, midIndex, endIndex);
}




void efficientRandomSortedList(long temp[], long s) {
    // Get a new random device
    randomizer device = new_randomizer();
    // Get a uniform distribution from 1 to 1000
    uniform_distribution range = new_distribution(1, 45000);

    for (long i = 0; i < s; i++) {
        // At every cell of the array, insert a randomly selected number
        // from distribution defined above
        temp[i] = sample(range, device);
    }

    // Now sort the array using insertion_sort

    merge_sort(temp, 0, s - 1);
}


#endif /* DataGen_h */

This is for class so unfortunately I can't change the data type that I'm working with. Any help or general critiques of my formatting would be helpful.

这是为了类,所以不幸的是我不能改变我正在使用的数据类型。对我的格式的任何帮助或一般批评都会有所帮助。

2 个解决方案

#1

If you are going to do merge that way, you might as well be doing selection sort; the merge steps are all quadratic and you are still doing a logarithmic number of them.

如果你打算以这种方式进行合并,你也可以选择排序;合并步骤都是二次的,你仍然在做对数。

In-place mergesort is tricky (and not as fast as mergesort). You should just merge into a temporary vector and then copy back over the original. Or avoid the copy by alternating between two vectors as you recurse.

就地mergesort很棘手(并不像mergesort那么快)。您应该只是合并到一个临时矢量,然后复制回原始。或者在你递归时通过在两个向量之间交替来避免复制。

#2

Bubble-sort is an O(n²) algorithm, which is slow. Merge-sort is O(nlogn) which is fast.

冒泡排序是一种O(n²)算法,它很慢。合并排序是O(nlogn),它很快。

To unserstand the spees of these algorithms see https://www.toptal.com/developers/sorting-algorithms

要了解这些算法的语言,请参阅https://www.toptal.com/developers/sorting-algorithms

#1