0

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.

Orion Johnson
  • 1
  • Can you include some performance numbers? Remember that merge sort has average performance of `O(N*lgN)`, so if your code scales to this, then nothing may be wrong. – Tim Biegeleisen Oct 08 '17 at 23:44
  • 3
    Your `merge` is quadratic, because of the way you move `O(n)` elements every time you need to insert. This kinda defeats the whole point. – Igor Tandetnik Oct 08 '17 at 23:45
  • *I have been looking through all of the threads here and couldn't seem to find a solution that worked.* -- You didn't search hard enough. Did you see [this thread](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c)? – PaulMcKenzie Oct 09 '17 at 00:48
  • merge-sort is best suited for linked lists, try [pivot-sort](https://en.wikipedia.org/wiki/Quicksort) for example for continuous data – sp2danny Oct 09 '17 at 00:50
  • @sp2danny does pivot sort work on larger datasets? such as up to 15 million randomized numbers? – Orion Johnson Oct 09 '17 at 02:28
  • @OrionJohnson: Just as well as any other O(N log N) algorithm. Better than mergesort, since mergesort require memory overhead – sp2danny Oct 09 '17 at 09:23
  • @OrionJohnson - side note, the code uses "end" as part of the names of indices, but those variables represent the "last" index as opposed to the "ending" index. You should change the names or change the code. – rcgldr Oct 09 '17 at 17:57
  • as mentioned in @nici answer, the merge part should not use insertion sort like method of shifting the array to insert elements. There is a wiki article with simple examples for both top down and bottom up [merge sort](https://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation) . – rcgldr Oct 09 '17 at 23:12

2 Answers2

0

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

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

jsn
  • 71
  • 4
0

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.

rici
  • 234,347
  • 28
  • 237
  • 341
  • In place merge sort is tricky, but if stability is not needed it can still have time complexity O(n log(n)) although slower than normal merge sort. Example java code shown in [this answer](https://stackoverflow.com/questions/46496692/algorithms-hybrid-mergesort-and-insertionsort-execution-time/46498454#46498454) of a hybrid in place merge / insertion sort. – rcgldr Oct 09 '17 at 18:38
  • @rcgldr: that's very pretty. – rici Oct 09 '17 at 18:40