Merge sort implementation using divide-and-conquer

Question

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?

Answer 1

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 b = mergeAndSort( rightHalfOfArray(array) ); return merge(a,b); } 

Answer 2

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'.