1
\$\begingroup\$

I was told in an interview to write a program for implementing merge sort on the concept of divide-and-conquer.

var myGlobalArray = undefined;

myGlobalArray = [8,4,17,2,1,32];
example01(myGlobalArray);

myGlobalArray = [48,14,17,2,11,132];
example01(myGlobalArray);

myGlobalArray = [45,14,5,2,1,12];
example01(myGlobalArray);

myGlobalArray = [45,-14,-5,2,1,-12];
example01(myGlobalArray);

myGlobalArray = [38,27,43,3,9,82,10];
example01(myGlobalArray);

myGlobalArray = [34,45,1,23,19,12,10];
example01(myGlobalArray);


function example01(myArray){
   var mainArray = [];

   // Divide
   createSubArray(myArray,0);

   // Conquer      
   mainArray = mergeArrays(mainArray);

   console.log(myArray+" => "+mainArray[0]);

   // creates an array which contains n arrays for n numbers present in myarray
   // i.e. if array = [ 34, 1, 27, 3 ] that the below method will return
   // [ [34], [1], [27], [3] ]
   function createSubArray(subArray,index){
        var localArray = [];

        if(subArray[index] !== undefined){
            localArray.push(subArray[index]);
            mainArray.push(localArray);
            createSubArray(subArray,++index); // dividing recursively   
        }       
   }//createSubArray


   // merge the arrays present i.e. 
   // if gblArray = [ [2,5], [1,7] ] 
   // then the below method will return
   // an merged array [ [1, 2, 5, 7] ]
   function mergeArrays(gblArray){
        var mergedArrays = [],
            main_array = gblArray,
            arr = [], 
            left_array = undefined, 
            right_array = undefined, 
            counter = 0, 
            nextCounter = 0;

        do{

            while(counter < main_array.length){
                nextCounter = counter + 1;

                if(main_array[nextCounter] !== undefined){

                    left_array = main_array[counter];
                    right_array = main_array[nextCounter];

                    // merge left and right arrays and sort it                      
                    arr = mergeAndSort(left_array,right_array);     

                    mergedArrays.push(arr);
                }else{
                    mergedArrays.push(main_array[counter]);
                }
                counter = nextCounter + 1;
            }

            main_array = mergedArrays;              
            mergedArrays = [];  
            counter = 0;
            nextCounter = 0;

        }while(main_array.length > 1);

        return main_array;
   }//mergeArrays


   // merges two array and sorts i.e.
   // if array1 = [1,23] and array2 = [4,12] than
   // the below method returns [1,4,12,23]
   function mergeAndSort(array1,array2){
        var array2Counter = 0, 
            array1Counter = 0, 
            mergedArray = [];

        while(array2Counter < array2.length && array1Counter < array1.length){

            if(array2[array2Counter] < array1[array1Counter]){
                mergedArray.push(array2[array2Counter]);
                array2Counter++;
            }else{
                mergedArray.push(array1[array1Counter]);
                array1Counter++;
            }
        }

        while(array1Counter < array1.length){
            mergedArray.push(array1[array1Counter]);
            array1Counter++;
        }

        while(array2Counter < array2.length){
            mergedArray.push(array2[array2Counter]);
            array2Counter++;
        }

        return mergedArray;
   } //mergeAndSort



}//example01

The output is:

8,4,17,2,1,32 => 1,2,4,8,17,32
48,14,17,2,11,132 => 2,11,14,17,48,132
45,14,5,2,1,12 => 1,2,5,12,14,45
45,-14,-5,2,1,-12 => -14,-12,-5,1,2,45
38,27,43,3,9,82,10 => 3,9,10,27,38,43,82
34,45,1,23,19,12,10 => 1,10,12,19,23,34,45

But by looking at my implemented merge-sort program, the inteviewer said that it doesn't follow the divide-and-conquer concept.

I tried to convince him that method mergeArrays and mergeAndSort do the divide-and-conquer, but he didn't agreed. Where am I going wrong?

\$\endgroup\$
2
\$\begingroup\$

To expand on CiaPan's answer. Your solution might look like:

result = mergeAndSort([8,4,17,2,1,32]);

You would write code that would do:

let a = mergeAndSort([8,4,17]);
let b = mergeAndSort([2,1,32]);
return merge(a, b);

This would be recursive, so mergeAndSort([8,4,17]) would do:

let a = mergeAndSort([8,4]);
let b = mergeAndSort([17]);
return merge(a, b);

Now mergeAndSort would be called with [8,4] which would be:

let a = mergeAndSort([8]);
let b = mergeAndSort([4]);
return merge(a, b);

Now lastly you have mergeAndSort([8]) which is trivially implemented as

return [8]

Or alternatively, in pseudocode:

function mergeAndSort(array) {
  if (array.length <= 1)
    return array;
  let a = mergeAndSort( leftHalfOfArray(array)  );
  let a = mergeAndSort( rightHalfOfArray(array) );
  return merge(a,b); 
}
\$\endgroup\$
  • \$\begingroup\$ Precisely. +1 Except I would call the routine e.g. sortByMerging instead of mergeAndSort, as the 'and' in the latter suggests sorting is done after merging. \$\endgroup\$ – CiaPan Mar 22 '17 at 12:46
1
\$\begingroup\$

The divide and conquer paradigm is based on recurring into subproblems: take a problem, divide it into a few (typically: two) smaller subproblems, solve each of them recursively, then join/merge results.

What you do is: split the problem recursively into a large amount of elementary, trivial problems, then iteratively pick them by pair, join and push back for further joining. It doesn't quite fit the template of 'divide – solve recursively – join solutions'.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.