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); 
}

• CiaPan: 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.

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