Merge Two Sorted Array Without Extra Space in Kotlin

To merge two sorted arrays without using extra space, you can use a modified version of the merge sort algorithm called the “in-place merge” algorithm. This algorithm works by iterating through the two arrays and comparing the elements at each index, then swapping them if necessary to ensure that the elements are in the correct order.

Here’s a step-by-step explanation of how to implement the in-place merge algorithm:

1. Iterate through each element in the first array, comparing it to the first element in the second array.
2. If the element in the first array is greater than the element in the second array, swap them.
3. After the swap, compare the swapped element from the first array with the element in the second array that comes after the swapped element, and swap them if necessary to maintain the sorted order.
4. Repeat steps 2 and 3 until the end of the first array is reached.
5. At this point, the first array will contain the merged elements in the correct order. You can simply return this array as the merged array.

Here’s an implementation of the in-place merge algorithm in Kotlin:

fun mergeInPlace(arr1: IntArray, arr2: IntArray): IntArray {
    var i = 0
    var j = 0
    while (i < arr1.size && j < arr2.size) {
        if (arr1[i] > arr2[j]) {
            // Swap arr1[i] and arr2[j]
            val temp = arr1[i]
            arr1[i] = arr2[j]
            arr2[j] = temp
            // Compare the swapped element with the next element in arr2
            var k = j + 1
            while (k < arr2.size && arr2[k] < temp) {
                arr2[k - 1] = arr2[k]
                k++
            }
            arr2[k - 1] = temp
        }
        i++
    }
    return arr1 + arr2
}
fun main(){
    val arr1 = intArrayOf(1, 3, 5, 7, 9)
	val arr2 = intArrayOf(2, 4, 6, 8, 10)
	val merged = mergeInPlace(arr1, arr2)
	println("Merged array: ${merged.joinToString(", ")}")
}

step of the in-place merge algorithm in more detail:

1. We start by initializing two pointers, i and j, to point to the first element of the two input arrays, arr1 and arr2, respectively.
2. We compare the element at arr1[i] with the element at arr2[j]. If arr1[i] is greater than arr2[j], we swap these two elements. This ensures that the element in arr1 is in the correct position relative to the elements in arr2.
3. After the swap, we need to make sure that the element that was swapped from arr1 is still in the correct position relative to the other elements in arr2. To do this, we start a new loop with a pointer k that starts at j + 1 (the index of the element in arr2 that comes after the swapped element). We then compare arr2[k] with the swapped element, and if arr2[k] is less than the swapped element, we swap these two elements. We continue this process until we find the correct position for the swapped element in arr2.
4. We repeat steps 2 and 3 until we have reached the end of either arr1 or arr2. At this point, we know that all the elements in the shorter array have been merged correctly into the longer array.
5. Finally, we concatenate the remaining elements in the two arrays to create the merged array. We can do this because we know that the elements in each array are already sorted.
6. In this example, the input arrays are [1, 3, 5, 7, 9] and [2, 4, 6, 8, 10]. The output will be Merged array: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, which is the merged array in sorted order.

By following these steps, we are able to merge two sorted arrays without using any extra space. The time complexity of this algorithm is O(mn), where m and n are the lengths of the two input arrays. However, the actual number of comparisons and swaps that need to be performed is much smaller than this worst-case bound, so this algorithm is generally quite efficient in practice.