12-Sorting-Merge/2-mergeSort-recursion.js at master · 4pmAlgorithm/12-Sorting-Merge · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
// Recrusive Merge Sort
// pseudo code

// 1. break up the array into halves until you have arrays that are empty or have one element
// 2. once you have smaller sorted arrays, merge those arrays with other sorted arrays until you are back at the full length of the array
// 3. once the array has been merged back together, return the merged(and sorted)array


function mergeArray(arr1, arr2){

    let result = [];
    let i = 0;
    let j = 0;

    while( i < arr1.length && j < arr2.length){
        if(arr1[i] < arr2[j]){
            result.push(arr1[i])
            //console.log(":::while1::", result)
            i++
        }else{
            result.push(arr2[j])
            //console.log(":::while1 else::", result)
            j++
        }
    }

    while( i < arr1.length ){
        result.push(arr1[i])
        //console.log("::::::::while2", result)
        i++
    }

    while( j < arr2.length) {
        result.push(arr2[j])
        //console.log("::::::::while3", result)
        j++
    }
    return result

}
//console.log(mergeArray([1,2,4], [3, 100,200,300]))


function mergeRecursion(arr){
    if(arr.length <= 1) return arr

    let mid = Math.floor(arr.length/2)
    let left = mergeRecursion(arr.slice(0, mid))
    console.log("::::::::::::::::::left", left)
    let right = mergeRecursion(arr.slice(mid))
    console.log("::::::::::::::::::right", right)

    return mergeArray(left, right)
}

console.log(mergeRecursion([3,4,5,8,   100,1,2,300,800]))


// function mergeRecursion(arr){
//     if(arr.length <=1) return arr;
//     let halfIdx = Math.floor(arr.length/2)
//     let arr1 = mergeRecursion(arr.slice(0, halfIdx))
//     let arr2 = mergeRecursion(arr.slice(halfIdx, arr.length))
//     return merge(arr1, arr2)
// }

// function merge(arr1, arr2){

//     let i = 0;
//     let j = 0;
//     let result = [];

//     while ( i < arr1.length && j < arr2.length){
//         if(arr1[i] < arr2[j]){
//             result.push(arr1[i])
//             i++
//         }else{
//             result.push(arr2[j])
//             j++
//         }
//     }

//     while(arr1.length > i){
//         result.push(arr1[i])
//         i++
//     }

//     while(arr2.length > j){
//         result.push(arr2[j])
//         j++
//     }
//     return result
// }

//console.log(mergeRecursion([2,3,4,22,33,44,55]))


// function mergeSort(arr){
//     if(arr.length <= 1) return arr;
//     let mid = Math.floor(arr.length/2);
//     let left = mergeSort(arr.slice(0,mid));
//     let right = mergeSort(arr.slice(mid));
//     return merge(left, right);
// }

// console.log(mergeSort([10,24,76,73]))