In-place merge sort

[Lacy9265]

I've written a program that is has in-place merge sort that does not require a temporary array to merge the two halves. The program also includes a <ctime> that times how long it takes for the array to be sorted. I have finished the code however I would like someone to look over it to make sure I did everything right. Like having the merge sort (no temporary array), clock_t working, and ect. The project includes a driver.cpp, driver.h, and MergeSort.cpp.

// driver.cpp
#include "Driver.h"
#include <stdio.h>
#include <ctime>
#include <iostream>


/* Driver program to test above functions */
int main()
{
    int array[] = { 12, 11, 13, 5, 6, 7};
    int array_size = sizeof(array) / sizeof(array[0]);

    clock_t start = clock();
    mergeSort(array, 0, array_size - 1);
    clock_t finish = clock();
    double doneTime = float(finish - start) / CLOCKS_PER_SEC;
    std::cout << "The time it took to store the array: ";
    std:: cout << doneTime << " seconds\n";

    std::cout << "Array Sorted:\n";
    printArray(array, array_size);
    
}


//driver.h
// Merges the two sub arrays of array
void merge(int array[], int start, int middle, int end);

// Sorts the left and right index of the array
void mergeSort(int array[], int left, int right);

// Prints the array after the array is sorted
void printArray(int array[], int size);



// MergeSort.cpp
#include "Driver.h"
#include <stdio.h>
#include <iostream>

// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
// Inplace Implementation
void merge(int array[], int start, int middle, int end)
{
    int start2 = middle + 1;

    // If the direct merge is already sorted
    if (array[middle] <= array[start2]) {
        return;
    }

    // Two pointers to maintain start
    // of both arrays to merge
    while (start <= middle && start2 <= end) {

        // If element 1 is in right place
        if (array[start] <= array[start2]) {
            start++;
        }
        else {
            int value = array[start2];
            int index = start2;

            // Shift all the elements between element 1
            // element 2, right by 1.
            while (index != start) {
                array[index] = array[index - 1];
                index--;
            }
            array[start] = value;

            // Update all the pointers
            start++;
            middle++;
            start2++;
        }
    }
}

/* l is for left index and r is right index of the
   sub-array of arr to be sorted */
void mergeSort(int array[], int left, int right)
{
    if (left < right) {

        // Same as (l + r) / 2, but avoids overflow
        // for large l and r
        int m = left + (right - left) / 2;

        // Sort first and second halves
        mergeSort(array, left, m);
        mergeSort(array, m + 1, right);

        merge(array, left, m, right);
    }
}


/* Function to print an array */
void printArray(int array[], int size)
{
    for (int i = 0; i < size; i++)
        std::cout << " " << array[i];  
   
}

[dutch]

It's not that hard to do an inplace merge if you aren't interested in performance.
If you want it to perform anything near the "real thing" then it's actually kind of hard

The program below compares your program and a simple bottom-up mergesort on random arrays of 100000 elements. The simple mergesort seems a lot faster.

#include <iostream>
#include <chrono>
#include <random>

const int Size = 100000;

void mergeSort(int array[], int left, int right);
void printArray(int array[], int size);
void mergesortX(int *a, int n);

class Clock
{
    using Clk = std::chrono::steady_clock;
    Clk clk;
    Clk::time_point mStart, mEnd;
public:
    Clock() { mStart = clk.now(); }
    Clk::time_point get_start() const { return mStart; }
    Clk::time_point get_end()   const { return mEnd;   }
    void start()  { mStart = clk.now(); }
    void end()    { mEnd   = clk.now(); }
    void end_ms() { end();  print_ms(); }
    void end_us() { end();  print_us(); }
    Clk::duration dur() const { return mEnd - mStart; }
    template<typename D>
    auto ticks() const
        { return std::chrono::duration_cast<D>(dur()).count(); }
    void print_ms() const
        { std::cout << ticks<std::chrono::milliseconds>() << "ms\n"; }
    void print_us() const
        { std::cout << ticks<std::chrono::microseconds>() << "us\n"; }
};

int main()
{
    std::default_random_engine rnd(std::random_device{}());
    std::uniform_int_distribution<> dist(0, Size * 10);

    auto a {new int[Size]};
    for (int i = 0; i < Size; ++i) a[i] = dist(rnd);

    Clock clk;
//    mergeSort(a, 0, Size - 1);
    mergesortX(a, Size);
    clk.end_us();

    if (Size <= 100) printArray(a, Size);
}

void merge(int array[], int start, int middle, int end)
{
    int start2 = middle + 1;
    if (array[middle] <= array[start2])
        return;
    while (start <= middle && start2 <= end) {
        if (array[start] > array[start2]) {
            int value = array[start2];
            for (int i = start2; i != start; --i)
                array[i] = array[i - 1];
            array[start] = value;
            ++middle;
            ++start2;
        }
        ++start;
    }
}

void mergeSort(int array[], int left, int right) {
    if (left < right) {
        int m = left + (right - left) / 2;
        mergeSort(array, left, m);
        mergeSort(array, m + 1, right);
        merge(array, left, m, right);
    }
}

void printArray(int array[], int size) {
    for (int i = 0; i < size; ++i) std::cout << ' ' << array[i];  
    std::cout << '\n';
}

void mergeX(int *a, int size, int istart, int n, int *buf) {
    int i = istart, j = istart + size, k = istart;
    const int iend = j, jend = j + size < n ? j + size : n;
    while (i < iend && j < jend)
        buf[k++] = a[i] <= a[j] ? a[i++] : a[j++];
    while (i < iend) buf[k++] = a[i++];
    while (j < jend) buf[k++] = a[j++];
    for (int x = istart; x < jend; ++x) a[x] = buf[x];
}

void mergesortX(int *a, int n) {
    auto buf = new int[n];
    for (int size = 1; size < n; size *= 2)
        for (int i = 0; i + size <= n; i += size * 2)
            mergeX(a, size, i, n, buf);
    delete[] buf;
}

[Lacy9265]

I'm just interested that I have in-place merge sort that works and that you can time how long the sort takes. Thank you for your example.

[dutch]

Additional timing shows it to perform worse than insertion sort, so apparently it's n-squared at best.
Insertion sort is "in-place", so you may as well just use it.

[helios]

Indeed. The innermost loop in merge() runs n * (n/2) times, where n = end - start. It's probably O(n^2 log n)