Merge Sort Algorithm

The Merge Sorted Array Algorithm is an efficient, stable, and comparison-based algorithm that is used to combine two or more sorted arrays into a single sorted array. This algorithm is a crucial part of the renowned Merge Sort, which is a divide-and-conquer sorting technique. The main idea behind the algorithm is to compare the first elements of the given sorted arrays and select the smallest element to be placed in the resulting merged array. This process is continued for the remaining elements in the given sorted arrays until all elements have been merged into the final sorted array. This algorithm is highly versatile and can be used to sort various data structures such as lists, arrays, and even large-scale data stored in databases or external storage. The efficiency of the Merge Sorted Array Algorithm lies in its linear time complexity, which is O(n+m), where n and m are the lengths of the two sorted arrays being merged. This is because the algorithm only needs to perform a single pass through both input arrays to generate the merged array. To implement the algorithm, two pointers or indices are used: one for each of the input arrays. These pointers start at the beginning of their respective arrays and are incremented as the elements are compared and added to the merged array. When one of the pointers reaches the end of its array, the remaining elements from the other array are added directly to the merged array, as they are already sorted. This algorithm can be implemented in various programming languages and can be easily adapted to handle additional constraints such as duplicate elements or custom comparison functions.
/*
 * Copyright (c) 2017 Kotlin Algorithm Club
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

package com.algorithmexamples.sorts

/**
 * Invented in 1945 by John von Neumann, merge sort is an efficient algorithm using the divide and conquer approach
 * which is to divide a big problem into smaller problems and solve them. Conceptually, a merge sort works as follows:
 * 1) Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
 * 2) Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining.
 */
@ComparisonSort
@StableSort
class MergeSort: AbstractSortStrategy() {
    override fun <T : Comparable<T>> perform(arr: Array<T>) {
        val aux = arr.clone()
        sort(arr, aux, 0, arr.size - 1)
    }

    private fun <T : Comparable<T>> sort(arr: Array<T>, aux: Array<T>, lo: Int, hi: Int) {
        if (hi <= lo) return
        val mid = (lo + hi) / 2
        sort(arr, aux, lo, mid)
        sort(arr, aux, mid + 1, hi)
        merge(arr, aux, lo, mid, hi)
    }

    private fun <T : Comparable<T>> merge(arr: Array<T>, aux: Array<T>, lo: Int, mid: Int, hi: Int) {
        System.arraycopy(arr, lo, aux, lo, hi - lo + 1)

        var i = lo
        var j = mid + 1
        for (k in lo..hi) {
            when {
                i > mid -> arr[k] = aux[j++]
                j > hi -> arr[k] = aux[i++]
                aux[j] < aux[i] -> arr[k] = aux[j++]
                else -> arr[k] = aux[i++]
            }
        }
    }
}

LANGUAGE:

DARK MODE: