Search code examples
javascriptreactjsmergesort

Merge Sort not working as expected in React


I have been debugging this code for hours but not getting whats wrong. items is the list of div elements with randomly initiated heights. Can someone help me, I am not able to find what is the problem with this code?

mergeSort1(l, r) {
    if (l < r) {
        let mid = Math.floor((l + r) / 2)
        this.mergeSort1(l, mid)
        this.mergeSort1(mid + 1, r)
        this.merge1(l, mid, r)
    }
}
merge1(l, mid, r) {
    let items = document.getElementsByClassName("item")
    items = Array.from(items)
    let left = items.slice(l, mid + 1)
    let right = items.slice(mid + 1, r + 1)
    let I = 0
    let J = 0
    let k = 0
    let t = []
    
    while (I < left.length && J < right.length) {
        if (parseInt(left[I].style.height) < parseInt(right[J].style.height)) {
            t.push(left[I].style.height)
            items[k + l].style.height = left[I].style.height
            I = I + 1
            k++
        } else {
            items[k + l].style.height = right[J].style.height
            t.push(right[J].style.height)
            J = J + 1
            k++
        }
    }
    while (I < left.length) {
        items[k + l].style.height = left[I].style.height
        k++
        t.push(left[I].style.height)
        I = I + 1
    }
    while (J < right.length) {
        items[k + l].style.height = right[J].style.height
        t.push(right[J].style.height)
        J = J + 1
        k++
    }
    console.log(t)
}
this.mergeSort1(0, this.state.arr.length - 1)

arr initialized in componentDidMount():

componentDidMount() {
    //this.step(this)
    
    var a = []
    for (var i = 0; i < 200; i++) {
        a.push(Math.round(Math.random() * 80))
    }
    this.setState({
        arr : a
    }, () => console.log(this.state.arr))
}

In render Method:

arr.map((h, i) => {
        return (
            <div className="item" key={i} style={{height:h+'vh'}}>
            </div>)
   })

Input:

arr = [ 52, 68, 34, 60, 60, 42, 72, 70, 76, 52, 53, 51, 62, 47, 73, 44, 30, 0, 27, 25, 45, 40, 39, 12, 33, 33, 41, 74, 10, 30, 48, 17, 21, 7, 29, 33, 32, 56, 79, 29, 36, 16, 79, 68, 44, 37, 34, 36, 4, 35, 59, 54, 2, 11, 56, 78, 25, 16, 9, 69, 39, 80, 48, 5, 34, 68, 68, 21, 48, 42, 75, 57, 8, 76, 20, 76, 59, 50, 3, 52, 13, 7, 19, 6, 20, 72, 76, 46, 23, 10, 43, 16, 50, 16, 15, 58, 63, 53, 11, 52, …]

Output(log of div heights after mergeSort):

["0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "0vh", "1vh", "1vh", "1vh", "35vh", "35vh", "66vh", "70vh"]

Solution

  • The problem is that you are attempting to sort an array of DOM elements by height, doing this by mutating the heights set in their style. This causes two problems:

    1. Array.from and items.slice will create new arrays, but they do not create copies of the DOM elements they contain. So when you assign to the height of an element, you are changing the height of an element somewhere else in items. This could be an item yet to be sorted.
    2. You are using React. You should let React control the DOM: you tell your components how to render themselves given some state and let React figure out how to change the DOM.

    If however you focus your code on sorting the list of numbers in this.state.arr, then your code works. In your merge1 method, get rid of your array items, replace any reference to items with this.state.arr and remove all the uses of .style.height and parseInt:

    merge1(l, mid, r) {
        let left = this.state.arr.slice(l, mid + 1)
        let right = this.state.arr.slice(mid + 1, r + 1)
        let I = 0
        let J = 0
        let k = 0
        let t = []
        
        while (I < left.length && J < right.length) {
            if (left[I] < right[J]) {
                t.push(left[I])
                this.state.arr[k + l] = left[I]
                I = I + 1
                k++
            } else {
                this.state.arr[k + l] = right[J]
                t.push(right[J])
                J = J + 1
                k++
            }
        }
        while (I < left.length) {
            this.state.arr[k + l] = left[I]
            k++
            t.push(left[I])
            I = I + 1
        }
        while (J < right.length) {
            this.state.arr[k + l] = right[J]
            t.push(right[J])
            J = J + 1
            k++
        }
        console.log(t)
    }
    

    You might also want to consider using variable names that are more descriptive than I, J, k, l, r or t, and also document your code to make it clear that the parameter r in mergeSort1 and merge1 is 'inclusive', i.e. it points to the last element to be sorted rather than the first element beyond that.