Time Divergence for Scaling Input Size (Quicksort vs Mergesort)

BenchmarkDemoA.java

// Search algorithm comparison benchmark experiment by Chris S

import java.time.Duration;
import java.time.Instant;
import java.util.Arrays;
import java.util.Random;
import java.util.ArrayList;

public class BenchmarkDemoA {

    public static int[] convertIntegers(ArrayList<Integer> integers) // Converts ArrayList<Integer> to int[]
    {
        int[] ret = new int[integers.size()];
        for (int i=0; i < ret.length; i++)
        {
            ret[i] = integers.get(i);
        }
        return ret;
    }

    public static void main(String[] args) {
        ArrayList<Integer> qNums = new ArrayList<Integer>(); // stores the growing list of integers for qSort
        ArrayList<Integer> mNums = new ArrayList<Integer>(); // stores the growing list of integers for mSort
        int qCount = 0;                                      // keep track of size of these lists
        int mCount = 0;
        for (int i = 0; i < 100; i++) {                      // main reporting loop
            Instant s, f;                   // init timekeeping vars
            long t;                         // init duration holder
            s = Instant.now();              // get current time at highest system supported resolution
            for (int j = 0; j < 1000; j++) {
                qNums.add(new Random().nextInt(999));qCount++;        // add one random int (max 999) per cycle
                QuickSort.qSort(convertIntegers(qNums), 0, qCount-1); // sort a clone array after EACH addition
            }
            f = Instant.now();              // 1000 steps complete now.
            t = Duration.between(s, f).toMillis();  // how much time did that take?
            System.out.println("qSort: Time to sort list of " + qCount + " ints: " + t);

            s = Instant.now();              // Let's repeat the process for merge sort now...
            for (int j = 0; j < 1000; j++) {
                mNums.add(new Random().nextInt(999));mCount++;
                MergeSort.sort(convertIntegers(mNums), 0, mCount-1);
            }
            f = Instant.now();
            t = Duration.between(s, f).toMillis();
            System.out.println("mSort: Time to sort list of " + qCount + " ints: " + t);

        }
    }

}

BenchmarkDemoA~info.md

Results of Demo A

The first demo, which timed steps of 1000 sort iterations (including the time to generate numbers and convert ArrayList to array) for both algorithms, produced results that seemed to perfectly fit the expectation that at some length, merge sort would become more efficient than quick sort. However, after further experimentation, I believe these results are coincidental and rather linked to the better handling of duplicate values by this merge sort implementation, which would be encountered with increasing frequency given the 3-digit integer range for the random generator.

BenchmarkDemoB.java

import java.time.Duration;
import java.time.Instant;
import java.util.Random;
import java.util.ArrayList;

public class BenchmarkDemoB {

    public static int[] convertIntegers(ArrayList<Integer> integers)  // convert ArrayList<Integer> to int[]
    {
        int[] ret = new int[integers.size()];
        for (int i = 0; i < ret.length; i++) {
            ret[i] = integers.get(i);
        }
        return ret;
    }

    public static void main(String[] args) {
        ArrayList<Integer> scalingDataset = new ArrayList<>();  // Integer data list
        int range = 99999;                            // max size for generated ints
        int intCount = 0;                             // list size counter
        Instant s, f;                                 // timekeeper (start, finish) vars
        long t;                                       // time elapsed / duration storage

        for (int j = 0; j < 8000000; j++) {           // prepopulate our list for a
            scalingDataset.add(new Random().nextInt(range)); // higher starting load
            intCount++;
        }

        for (int i = 0; i < 10000; i++) {             // MAIN REPORTING LOOP (stop manually
                                                      // when enough console output collected)
            for (int j = 0; j < 800000; j++) {        // add (loop range) new integers to list
                scalingDataset.add(new Random().nextInt(range));
                intCount++;                           // and keep count
            }

            s = Instant.now();                        // start timekeeping for quicksort
            QuickSort.qSort(convertIntegers(scalingDataset), 0, intCount - 1);
            f = Instant.now();                        // finish timekeeping for quicksort
            t = Duration.between(s, f).toMillis();    // get difference (duration of algo)
            System.out.println("qSort: Time to sort list of " + intCount + " ints: " + t);

            s = Instant.now();                        // repeat for mergesort
            MergeSort.sort(convertIntegers(scalingDataset), 0, intCount - 1);
            f = Instant.now();
            t = Duration.between(s, f).toMillis();
            System.out.println("mSort: Time to sort list of " + intCount + " ints: " + t);

        }
    }
}

BenchmarkDemoB~info.md

Results of Demo B

The second demo differs in that it calculates time for single algorithm runs with each step, and does not include time for the random generation (arrayList >> int[] time is still included). The length of random numbers was also increased to 5 to increase the load, but as mentioned in analysis of Demo A, the length of these numbers (and related likeliness of collisions/duplicates) may be the driving factor behind MergeSort surpassing QuickSort in performance.

What if we lowered the likelihood of duplicates by increasing the random range?

With longer integer values and thus less collisions, qSort seems to outperform mSort by a significant margin, at least to the extent I was able to benchmark. Perhaps the theoretical point at which mSort becomes faster than qSort is simply for much higher values than a low-power laptop can reach and measure?

MergeSort.java

// From https://www.geeksforgeeks.org/merge-sort/ (by Rajat Mishra)

public class MergeSort {
    // Merges two subarrays of arr[].
    // First subarray is arr[l..m]
    // Second subarray is arr[m+1..r]
    static void merge(int arr[], int l, int m, int r) {
        // Find sizes of two subarrays to be merged
        int n1 = m - l + 1;
        int n2 = r - m;

        /* Create temp arrays */
        int L[] = new int[n1];
        int R[] = new int[n2];

        /*Copy data to temp arrays*/
        for (int i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];


        /* Merge the temp arrays */

        // Initial indexes of first and second subarrays
        int i = 0, j = 0;

        // Initial index of merged subarry array
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        /* Copy remaining elements of L[] if any */
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        /* Copy remaining elements of R[] if any */
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    // Main function that sorts arr[l..r] using
    // merge()
    static void sort(int arr[], int l, int r) {
        if (l < r) {
            // Find the middle point
            int m = (l + r) / 2;

            // Sort first and second halves
            sort(arr, l, m);
            sort(arr, m + 1, r);

            // Merge the sorted halves
            merge(arr, l, m, r);
        }
    }

    /* A utility function to print array of size n */
    static void printArray(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    // Driver method
    public static void main(String args[]) {
        int arr[] = {12, 11, 13, 5, 6, 7};

        System.out.println("Given Array");
        printArray(arr);

        MergeSort ob = new MergeSort();
        ob.sort(arr, 0, arr.length - 1);

        System.out.println("\nSorted array");
        printArray(arr);
    }
}
/* This code is contributed by Rajat Mishra */

QuickSort.java

// From https://www.geeksforgeeks.org/quick-sort/

// Java program for implementation of QuickSort
import java.util.*;

public class QuickSort {
    /* This function takes last element as pivot,
    places the pivot element at its correct
    position in sorted array, and places all
    smaller (smaller than pivot) to left of
    pivot and all greater elements to right
    of pivot */
    static int partition(int arr[], int low, int high)
    {
        int pivot = arr[high];
        int i = (low - 1); // index of smaller element
        for (int j = low; j <= high - 1; j++) {
            // If current element is smaller than or
            // equal to pivot
            if (arr[j] <= pivot) {
                i++;

                // swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // swap arr[i+1] and arr[high] (or pivot)
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    /* The main function that implements QuickSort()
    arr[] --> Array to be sorted,
    low --> Starting index,
    high --> Ending index */
    static void qSort(int arr[], int low, int high)
    {
        if (low < high) {
            /* pi is partitioning index, arr[pi] is
            now at right place */
            int pi = partition(arr, low, high);

            // Recursively sort elements before
            // partition and after partition
            qSort(arr, low, pi - 1);
            qSort(arr, pi + 1, high);
        }
    }

    Driver code
    public static void main(String args[])
    {
        int n = 5;
        int arr[] = { 4, 2, 6, 9, 2 };

        qSort(arr, 0, n - 1);

        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

~ParseConsoleOut.py

# ParseConsoleOut.py
# Takes input with lines in the form "qSort: Time to sort list of 14400000 ints: 2943"
# First line should have value for qSort, just copy / paste some amt of line pairs from console out
# into a text file and open from dialog window. New CSV with same name will be created in script folder.

# "Why do work in Java now when you can do it in Python later?" - Gandhi

import csv
from tkinter import *
from tkinter.filedialog import askopenfilename

root = Tk()
root.withdraw()

fileinname = askopenfilename()
root.destroy()

if "." in fileinname:
    a = fileinname.find('.')
    fileoutname = fileinname[:a]+".csv"
if "/" in fileinname:
    a = fileinname.rfind('/')
    fileoutname = fileoutname[a+1:]
filein= open(fileinname,"r")

qSortTimesMS=[]
mSortTimesMS=[]
forIntArraySize=[]

contents = filein.readlines()
filein.close()
for line in contents:
    if "qSort" in line:
        a, b = line.find('list of '), line.find(' ints:')
        forIntArraySize.append(line[a+8:b])
        a, b = line.find('nts: '), line.find('/n')
        qSortTimesMS.append(line[a+5:b])
    elif "mSort" in line:
        a, b = line.find('nts: '), line.find('/n')
        mSortTimesMS.append(line[a+5:b])

fileout = open(fileoutname, 'w+',  newline='')
print("Parsed file successfully -- input len range was [",forIntArraySize[0],", ",forIntArraySize[-1],"]:\n")
print("Quick sort times:\n", qSortTimesMS)
print("Merge sort times:\n", mSortTimesMS)

print("CSV was saved as '", fileoutname, "' in script directory.")
writer = csv.writer(fileout)
writer.writerows(zip(forIntArraySize, qSortTimesMS, mSortTimesMS))

fileout.close()