Merge Two Sorted Linked Lists Using Bash

This Bash script demonstrates the process of merging two sorted linked lists, represented as arrays, into a single sorted list. The merging process maintains the order of elements ensuring the resulting list is sorted.

Bash Script Code

#!/bin/bash

# Function to merge two sorted lists
merge_lists() {
    local -a list1=("${!1}") # First sorted list
    local -a list2=("${!2}") # Second sorted list
    local -a merged=()

    local i=0
    local j=0

    # Merge the lists
    while [[ $i -lt ${#list1[@]} && $j -lt ${#list2[@]} ]]; do
        if [[ ${list1[$i]} -le ${list2[$j]} ]]; then
            merged+=(${list1[$i]})
            ((i++))
        else
            merged+=(${list2[$j]})
            ((j++))
        fi
    done

    # If elements remain in list1, append them
    while [[ $i -lt ${#list1[@]} ]]; do
        merged+=(${list1[$i]})
        ((i++))
    done

    # If elements remain in list2, append them
    while [[ $j -lt ${#list2[@]} ]]; do
        merged+=(${list2[$j]})
        ((j++))
    done

    echo "Merged List: ${merged[@]}"
}

# Example usage
list1=(1 4 6 8)
list2=(2 3 5 7 9)

# Call the function with array names
merge_lists list1[@] list2[@]

Explanation of the Code

The script defines a function merge_lists that merges two sorted lists (arrays):

1. Initialization: The function starts by initializing indices for both lists and an empty array for the merged list.
2. Merging Process: It uses a loop to compare elements of both lists, appending the smaller (or equal) element to the merged list and incrementing the respective index.
3. Appending Remaining Elements: After one of the lists is exhausted, the remaining elements from the other list are appended to the merged list.
4. Output: Finally, the merged list is printed to the console.

Output and Use Case

The script, when run with the example lists provided, will output “Merged List: 1 2 3 4 5 6 7 8 9”, showing the correct merging of the two sorted lists.