1- import Sort from ' ../Sort' ;
1+ import Sort from " ../Sort" ;
22
33export default class MergeSort extends Sort {
44sort ( originalArray ) {
@@ -24,36 +24,42 @@ export default class MergeSort extends Sort {
2424}
2525
2626mergeSortedArrays ( leftArray , rightArray ) {
27- let sortedArray = [ ] ;
27+ const sortedArray = [ ] ;
2828
29- //In case if arrays are not of size 1.
30- while ( leftArray . length && rightArray . length ) {
31- let minimumElement = null ;
29+ //Use array pointers to exclude old elements after they have been added to the sorted array
30+ let leftIndex = 0 ;
31+ let rightIndex = 0 ;
3232
33- // Find minimum element of two arrays.
34- if ( this . comparator . lessThanOrEqual ( leftArray [ 0 ] , rightArray [ 0 ] ) ) {
35- minimumElement = leftArray . shift ( ) ;
36- } else {
37- minimumElement = rightArray . shift ( ) ;
38- }
33+ while ( leftIndex < leftArray . length && rightIndex < rightArray . length ) {
34+ // Find the minimum element between the left and right array
35+ if (
36+ this . comparator . lessThanOrEqual (
37+ leftArray [ leftIndex ] ,
38+ rightArray [ rightIndex ]
39+ )
40+ ) {
41+ sortedArray . push ( leftArray [ leftIndex ] ) ;
3942
40- //Call visiting callback.
41- this . callbacks . visitingCallback ( minimumElement ) ;
43+ //Increment index pointer to the right
44+ leftIndex += 1 ;
4245
43- // Push the minimum element of two arrays to the sorted array.
44- sortedArray . push ( minimumElement ) ;
45- }
46+ // Call visiting callback.
47+ this . callbacks . visitingCallback ( leftArray [ leftIndex ] ) ;
48+ } else {
49+ sortedArray . push ( rightArray [ rightIndex ] ) ;
4650
47- // If one of two array still have elements we need to just concatenate
48- // this element to the sorted array since it is already sorted.
49- if ( leftArray . length ) {
50- sortedArray = sortedArray . concat ( leftArray ) ;
51- }
51+ // Increment index pointer to the right
52+ rightIndex += 1 ;
5253
53- if ( rightArray . length ) {
54- sortedArray = sortedArray . concat ( rightArray ) ;
54+ // Call visiting callback.
55+ this . callbacks . visitingCallback ( rightArray [ rightIndex ] ) ;
56+ }
5557}
5658
57- return sortedArray ;
59+ // There will be one element remaining from either the left OR the right
60+ // Concatenate the remaining element into the sorted array
61+ return sortedArray
62+ . concat ( leftArray . slice ( leftIndex ) )
63+ . concat ( rightArray . slice ( rightIndex ) ) ;
5864}
5965}