// let arr = [64, 25, 12, 22, 11]

// function selection_sort(arr) {
//     for (let i = 0; i < arr.length-1; i++) {
//         min_idx = i
//         for (let j = i+1; j < arr.length; j++) {
//             if (arr[i] < arr[min_idx]) {
//                 min_idx = j
//             }
//             let temp = arr[min_idx];
//             arr[min_idx] = arr[i];
//             arr[i] = temp;
//         }
//     }
//     return arr
// }

// console.log(selection_sort(arr))

console.log("============================Selection sort=====================")

let arr = [64, 25, 12, 22, 11]

function selectionSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        let min_idx = i;
        for (let j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        // Swap the found minimum element with the first element
        [arr[i], arr[min_idx]] = [arr[min_idx], arr[i]];
    }
    return arr;
}

console.log(selectionSort(arr))

console.log("\n")

console.log("============================Bubble sort========================")

let arr1 = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

function bubbleSort(arr) {
    for (let i = 0; i < arr.length-1; i++) {
        let swapped = false;
        for (let j = 0; j < arr.length-1; j++) {
            if (arr[j] > arr[j+1]) {
               [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
                swapped = true
            }
        }
        if (!swapped) {
            break
        }
    }
    return arr
}

console.log(bubbleSort(arr1))

console.log("\n")

console.log("============================Insertion sort========================")

arr2 = [23,1,10,5,2]

function insertionSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        let key = arr[i]
        j = i -1

        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j]
            j -= 1
        }
        arr[j + 1] = key
    }
    return arr
}

console.log(insertionSort(arr2))

console.log("\n")

console.log("============================Merge sort========================")

// Function to merge two halves
function merge(arr, low, mid, high) {
    let nums = [];
    let left = low, right = mid + 1;

    // Merge the two halves
    while (left <= mid && right <= high) {
        if (arr[left] < arr[right]) {
            nums.push(arr[left]);
            left++;
        } else {
            nums.push(arr[right]);
            right++;
        }
    }

    // Add remaining elements from the left half
    while (left <= mid) {
        nums.push(arr[left]);
        left++;
    }

    // Add remaining elements from the right half
    while (right <= high) {
        nums.push(arr[right]);
        right++;
    }

    // Copy sorted elements back to the original array
    for (let i = low; i <= high; i++) {
        arr[i] = nums[i - low];
    }
}

// Function to perform merge sort
function mergeSort(arr, low, high) {
    if (low >= high) {
        return;
    }

    let mid = Math.floor((low + high) / 2);

    // Recursively sort first and second halves
    mergeSort(arr, low, mid);
    mergeSort(arr, mid + 1, high);

    // Merge the two sorted halves
    merge(arr, low, mid, high);
}

// Driver code to test the merge sort
let arr3 = [12, 11, 13, 5, 6, 7];

mergeSort(arr3, 0, arr3.length - 1);

console.log("Sorted array:", arr3);