sorting-visualizer/mergeSort.js at main · bmcardona/sorting-visualizer · 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
119
120
121
122
123
124
125
126
127

// function mergeSortedArrays(leftHalf, rightHalf) {
//   const sortedArray = new Array(leftHalf.length + rightHalf.length);
//   let k = 0;
//   let i = 0;
//   let j = 0;
//   while (i < leftHalf.length && j < rightHalf.length) {
//     if (leftHalf[i] <= rightHalf[j]) {
//       sortedArray[k++] = leftHalf[i++];
//     } else {
//       sortedArray[k++] = rightHalf[j++];
//     }
//   }
//   while (i < leftHalf.length) {
//     sortedArray[k++] = leftHalf[i++];
//   }
//   while (j < rightHalf.length) {
//     sortedArray[k++] = rightHalf[j++]
//   }
//   return sortedArray;
// }

// async function mergeSort(array) {
//   if (array.length <= 1) return array;
//   const middleIdx = Math.floor(array.length / 2);
//   const leftHalf = array.slice(0, middleIdx);
//   const rightHalf = array.slice(middleIdx);
//   return mergeSortedArrays(mergeSort(leftHalf), mergeSort(rightHalf));
// }

// mergeSortButton.addEventListener('click', () => {
//   var nodes = Array.prototype.slice.call(document.querySelector(".createColumns").children);
//   async function repeatChain(times, chain) {
//     for (let i = 0; i < times; i++) {
//       await chain(nodes);
//     }
//   }
//   repeatChain(1, mergeSort)
//   })


function mergeSortHelper(mainArray, startIdx, endIdx, auxiliaryArray) {
  if (startIdx == endIdx) {
    return
  }
  const middleIdx = Math.floor((startIdx + endIdx) / 2);
  mergeSortHelper(auxiliaryArray, startIdx, middleIdx, mainArray);
  mergeSortHelper(auxiliaryArray, middleIdx + 1, endIdx, mainArray);
  doMerge(mainArray, startIdx, middleIdx, endIdx, auxiliaryArray);
}

function doMerge(mainArray, startIdx, middleIdx, endIdx, auxiliaryArray) {
  let k = startIdx;
  let i = startIdx;
  let j = middleIdx + 1;
  while (i <= middleIdx && j <= endIdx) {
    if (auxiliaryArray[i] <= auxiliaryArray[j]) {
      mainArray[k++] = auxiliaryArray[i++];
    } else {
      mainArray[k++] = auxiliaryArray[j++];
    }
  }
  while (i <= middleIdx) {
    mainArray[k++] = auxiliaryArray[i++];
  }
  while (j <= endIdx) {
    mainArray[k++] = auxiliaryArray[j++];
  }
}

function mergeSort(array) {
  if (array.length <= 1) {
    return array;
  }
  const auxiliaryArray = array.slice();
  mergeSortHelper(array, 0, array.length - 1, auxiliaryArray);
  return array
}

// function mergeSortHelper(mainArray, startIdx, endIdx, auxiliaryArray) {
//   if (startIdx == endIdx) {
//     return
//   }
//   const middleIdx = Math.floor((startIdx + endIdx) / 2);
//   mergeSortHelper(auxiliaryArray, startIdx, middleIdx, mainArray);
//   mergeSortHelper(auxiliaryArray, middleIdx + 1, endIdx, mainArray);
//   doMerge(mainArray, startIdx, middleIdx, endIdx, auxiliaryArray);
// }

// function doMerge(mainArray, startIdx, middleIdx, endIdx, auxiliaryArray) {
//   let k = startIdx;
//   let i = startIdx;
//   let j = middleIdx + 1;
//   while (i <= middleIdx && j <= endIdx) {
//     if (auxiliaryArray[i].style.height <= auxiliaryArray[j].style.height) {
//       mainArray[k++].style.height = auxiliaryArray[i++].style.height;
//     } else {
//       mainArray[k++].style.height = auxiliaryArray[j++].style.height;
//     }
//   }
//   while (i <= middleIdx) {
//     mainArray[k++].style.height = auxiliaryArray[i++].style.height;
//   }
//   while (j <= endIdx) {
//     mainArray[k++].style.height = auxiliaryArray[j++].style.height;
//   }
// }

// function mergeSort(array) {
//   if (array.length <= 1) {
//     return array;
//   }
//   const auxiliaryArray = array.slice();
//   mergeSortHelper(array, 0, array.length - 1, auxiliaryArray);
//   return array
// }

// mergeSortButton.addEventListener('click', () => {
//   var nodes = Array.prototype.slice.call(document.querySelector(".createColumns").children);
//   async function repeatChain(times, chain) {
//     for (let i = 0; i < times; i++) {
//       await chain(nodes);
//     }
//   }
//   repeatChain(1, mergeSort)
//   })