Skip to content

Instantly share code, notes, and snippets.

@Veeyikpong
Last active December 14, 2022 06:53
Show Gist options
  • Save Veeyikpong/bb4e97ccbcf7473afe44cecfd9434726 to your computer and use it in GitHub Desktop.
Save Veeyikpong/bb4e97ccbcf7473afe44cecfd9434726 to your computer and use it in GitHub Desktop.
Merge sort in Kotlin
sortArray(intArrayOf(5, 2, 3, 1, 5, 6))
fun sortArray(nums: IntArray): IntArray {
mergeSort(nums, 0, nums.size - 1)
return nums
}
fun mergeSort(nums: IntArray, left: Int, right: Int) {
if (right <= left) return
val mid = (left + right) / 2
mergeSort(nums, left, mid)
mergeSort(nums, mid + 1, right)
merge(nums, left, right)
}
fun merge(nums: IntArray, leftIndex: Int, rightIndex: Int) {
val mid = ((leftIndex + rightIndex) / 2)
val intArray = IntArray((rightIndex - leftIndex) + 1)
var leftPointer = leftIndex
var rightPointer = mid + 1
var currentTempIndex = 0
while (leftPointer <= mid && rightPointer <= rightIndex) {
if (nums[leftPointer] > nums[rightPointer]) {
intArray[currentTempIndex] = nums[rightPointer]
rightPointer++
currentTempIndex++
} else {
intArray[currentTempIndex] = nums[leftPointer]
leftPointer++
currentTempIndex++
}
}
while (leftPointer <= mid) {
intArray[currentTempIndex] = nums[leftPointer]
leftPointer++
currentTempIndex++
}
while (rightPointer <= rightIndex) {
intArray[currentTempIndex] = nums[rightPointer]
rightPointer++
currentTempIndex++
}
for (i in leftIndex..rightIndex) {
nums[i] = intArray[i - leftIndex]
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment