Code to analyse time for various sorting algorithms

SortingAnalyser.kt

import java.util.*


fun main() {
    println("Analyzing algorithms...")

    val array = IntArray(1000000) { Random().nextInt() }

    analyseAlgorithms("quikSort" , { quikSort(it) }, array)
    analyseAlgorithms("mergeSort" , { mergesort(it) }, array)
    analyseAlgorithms("heapShort" , { heapSort(it) }, array)
    analyseAlgorithms("timShort" , { timeShort(it) }, array)

    analyseAlgorithms("selectionSort" , { selectionSort(it) }, array)
    analyseAlgorithms("insertionSort" , { insertSort(it) }, array)
    analyseAlgorithms("bubbleSort" , { bubbleSort(it) }, array)

}

fun analyseAlgorithms(name : String, sortingFunction : (IntArray) -> Unit = {}, arr: IntArray){
    val timeBefore = System.currentTimeMillis();

    sortingFunction.invoke(arr)

    val timeAfter = System.currentTimeMillis()

    println("Time taken  $name: ${timeAfter - timeBefore}")
}

fun quikSort(arr: IntArray){

    fun quikSort(arr: IntArray, start: Int, end: Int) {

        fun partition(arr: IntArray, start: Int, end: Int): Int {
            val pivot = arr[end]
            var pIndex = start
            for (i in start until end) {
                if (arr[i] <= pivot) {
                    swap(arr, i, pIndex)
                    pIndex++
                }
            }
            swap(arr, pIndex, end)
            return pIndex
        }

        if (start < end) {
            val pIndex = partition(arr, start, end)
            quikSort(arr, start, pIndex - 1)
            quikSort(arr, pIndex + 1, end)
        }
    }

    quikSort(arr, 0, arr.size - 1)
}

fun mergesort(arr: IntArray) {
    fun merge(arr: IntArray, left: IntArray, right: IntArray) {
        val nL = left.size
        val nR = right.size
        var i = 0
        var j = 0
        var k = 0
        while (i < nL && j < nR) {
            if (left[i] <= right[j]) {
                arr[k] = left[i]
                i++
            } else {
                arr[k] = right[j]
                j++
            }
            k++
        }
        while (i < nL) {
            arr[k] = left[i]
            i++
            k++
        }
        while (j < nR) {
            arr[k] = right[j]
            j++
            k++
        }
    }

    val n = arr.size
    if (n < 2) return
    val mid = n / 2
    val left = IntArray(mid)
    val right = IntArray(n - mid)
    for (i in 0 until mid) left[i] = arr[i]
    for (i in mid until n) right[i - mid] = arr[i]
    mergesort(left)
    mergesort(right)
    merge(arr, left, right)
}

fun heapSort(arr: IntArray) {
    
    fun heapify(arr: IntArray, N: Int, i: Int) {
        var largest = i
        val l = 2 * i + 1
        val r = 2 * i + 2

        if (l < N && arr[l] > arr[largest]) largest = l

        if (r < N && arr[r] > arr[largest]) largest = r

        if (largest != i) {
            val swap = arr[i]
            arr[i] = arr[largest]
            arr[largest] = swap
            heapify(arr, N, largest)
        }
    }
    
    val N = arr.size

    for (i in N / 2 - 1 downTo 0) heapify(arr, N, i)

    for (i in N - 1 downTo 1) {
        val temp = arr[0]
        arr[0] = arr[i]
        arr[i] = temp

        heapify(arr, i, 0)
    }
}

fun selectionSort(arr: IntArray) {
    val n = arr.size
    for (i in 0 until n - 1) {
        var min_idx = i
        for (j in i + 1 until n) if (arr[j] < arr[min_idx]) min_idx = j
        swap(arr, min_idx, i)
    }
}

fun insertSort(array: IntArray) {
    for ((i, value) in array.withIndex()) {
        var j = i
        while (j > 0) {
            if (array[j] < array[j - 1]) {
                swap(array, i, j - 1)
            }
            j--
        }

    }
}

fun bubbleSort(arr: IntArray) {
    val n = arr.size
    for (i in 0 until n - 1)
        for (j in 0 until n - i - 1)
            if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1)
    }
}

object TimShort {

    var MIN_MERGE = 32

    private fun minRunLength(n: Int): Int {
        var n = n
        assert(n >= 0)

        var r = 0
        while (n >= MIN_MERGE) {
            r = r or (n and 1)
            n = n shr 1
        }
        return n + r
    }

    private fun insertionSort(
        arr: IntArray, left: Int,
        right: Int
    ) {
        for (i in left + 1..right) {
            val temp = arr[i]
            var j = i - 1
            while (j >= left && arr[j] > temp) {
                arr[j + 1] = arr[j]
                j--
            }
            arr[j + 1] = temp
        }
    }

    fun merge(
        arr: IntArray, l: Int,
        m: Int, r: Int
    ) {
        val len1 = m - l + 1
        val len2 = r - m
        val left = IntArray(len1)
        val right = IntArray(len2)
        for (x in 0 until len1) {
            left[x] = arr[l + x]
        }
        for (x in 0 until len2) {
            right[x] = arr[m + 1 + x]
        }
        var i = 0
        var j = 0
        var k = l

        while (i < len1 && j < len2) {
            if (left[i] <= right[j]) {
                arr[k] = left[i]
                i++
            } else {
                arr[k] = right[j]
                j++
            }
            k++
        }

        while (i < len1) {
            arr[k] = left[i]
            k++
            i++
        }

        while (j < len2) {
            arr[k] = right[j]
            k++
            j++
        }
    }

    fun timSort(arr: IntArray, n: Int) {
        val minRun = minRunLength(MIN_MERGE)

        var i = 0
        while (i < n) {
            insertionSort(
                arr, i,
                Math.min(i + MIN_MERGE - 1, n - 1)
            )
            i += minRun
        }

        var size = minRun
        while (size < n) {
            var left = 0
            while (left < n) {
                val mid = left + size - 1
                val right = Math.min(
                    left + 2 * size - 1,
                    n - 1
                )
                if (mid < right) merge(arr, left, mid, right)
                left += 2 * size
            }
            size *= 2
        }
    }
}

fun timeShort(arr: IntArray) {
    TimShort.timSort(arr, arr.size)
}

private fun swap(array: IntArray, index1: Int, index2: Int) {
    val temp = array[index1]
    array[index1] = array[index2]
    array[index2] = temp
}