Merge Sort on Linked List in Kotlin

by

To implement merge sort on a linked list, you can follow these steps:

  1. Define a Node class to represent a node in the linked list. Each node should have a data property to store its value, and a next property to point to the next node in the list.
  2. Define a mergeSort function that takes the head of the linked list as an argument and returns the sorted linked list.
  3. In the mergeSort function, first, check if the linked list is empty or has only one element, in which case it is already sorted and can be returned as is.
  4. Otherwise, divide the linked list into two halves using a split function that uses the slow and fast pointer technique.
  5. Recursively call the mergeSort function on the two halves to sort them.
  6. Merge the two sorted halves using a merge function. The merge function takes two sorted linked lists as arguments and returns the merged sorted linked list.
  7. In the merge function, create a dummy node to act as the head of the merged list. Traverse the two linked lists simultaneously, comparing the values of the nodes at each step and appending the smaller node to the merged list.
  8. After one of the lists is exhausted, append the remaining nodes of the other list to the merged list.
Kotlin
class Node(var data: Int, var next: Node? = null)

fun mergeSort(head: Node?): Node? {
    // Check for empty list or single element list
    if (head == null || head.next == null) {
        return head
    }
    
    // Divide the list into two halves
    val (left, right) = split(head)
    
    // Recursively sort the two halves
    val sortedLeft = mergeSort(left)
    val sortedRight = mergeSort(right)
    
    // Merge the two sorted halves
    return merge(sortedLeft, sortedRight)
}

fun split(head: Node?): Pair<Node?, Node?> {
    var slow = head
    var fast = head?.next
    
    while (fast != null) {
        fast = fast.next?.next
        if (fast != null) {
            slow = slow?.next
        }
    }
    
    val left = head
    val right = slow?.next
    slow?.next = null
    
    return Pair(left, right)
}

fun merge(left: Node?, right: Node?): Node? {
    // Create a dummy node to act as the head of the merged list
    val dummy = Node(0)
    var current = dummy
    
    var leftCurrent = left
    var rightCurrent = right
    
    // Traverse the two linked lists simultaneously and append the smaller node to the merged list
    while (leftCurrent != null && rightCurrent != null) {
        if (leftCurrent.data < rightCurrent.data) {
            current.next = leftCurrent
            leftCurrent = leftCurrent.next
        } else {
            current.next = rightCurrent
            rightCurrent = rightCurrent.next
        }
        current = current.next!!
    }
    
    // Append the remaining nodes of the other list to the merged list
    if (leftCurrent != null) {
        current.next = leftCurrent
    } else {
        current.next = rightCurrent
    }
    
    return dummy.next
}

// Example usage
fun main() {
    // Create an unsorted linked list
    val head = Node(3)
    head.next = Node(2)
    head.next?.next = Node(1)
    head.next?.next?.next = Node(4)

    // Sort the linked list using merge sort
    val sortedList = mergeSort(head)

    // Print the sorted linked list
    var current = sortedList
    while (current != null) {
        print("${current.data} ")
        current = current.next
    }
}

The linked list before sorting : 3 2 1 4

Output : 1 2 3 4

Leave a Comment