celestelayne/divide-conquer-sort-f52.md

## divide-conquer-sort-f52.md

      
    Raw
  

              divide-conquer-sort-f52.md
            
          
    Q: Write a function that takes a list of integers and returns the 4 highest in O(n) time.
A: Here, I use the merge sort algorithm since it uses O(n) space complexity and O(log(n)) runtime complexity. The following is my approach:

First, divide the array into halves:

arr = [1, 5, 6, 11, 3, 4, 8, 13];

const mergeSort = (arr) => {
// end function when array consists of only one element
    if (arr.length === 1){
        return arr
    }
// divide the array in half, taking into account the length of the array may be an odd number
    const middle = Math.floor(arr.length / 2);
// create two arrays called left and right
    const left = arr.slice(0, middle);
    const right = arr.slice(middle, arr.length);
// pass the two arrays into the merge helper function
    return merge(left, right)
}

Then, merge the individual arrays using a helper function merge algorithm:

// O(n) algorithms have out of place complexity and need an extra array into which to sort the elements
    let result = [];
    let idxLeft = 0
    let idxRight = 0
    
// iterate over the left and right arrays as long as the index is less than the length of the array 
    while (idxLeft < left.length && idxRight < right.length) {

// compare the elements in each array starting from index 0
// if the number on the left is less than the number on the right
     if (left[idxLeft] <= right[idxRight]) {
// push the left element into the result array
         result.push(left[idxLeft]);
// increment the index
         idxLeft++
     } else {
// otherwise, push the right element into the result array
         result.push(right[idxRight]);
// increment the index (0 becomes 1, 1 becomes 2 ... )
         idxRight++
     }
// in the result concatenate the sorted left and right arrays
        let mergedArr = result.concat(left.slice(idxLeft).concat(right.slice(idxRight)))
// pass the newly merged array and number of items to return, into the helper function
        fourLargest(mergedArr, 4)
    }

Finally, return the 4 largest elements in the now sorted and merged array:

const fourLargest = (arr, n) => {
// the slice method is used to return the four elements from the end of the sorted array 
    let sliced = arr.slice(-n);
    console.log(sliced)
}

Don't forget to call the mergeSort function :-)

// call the mergeSort function and pass in the array to be sorted
mergeSort(arr)