This semester we learned about Divide and Conquer in which the problem is divided into subproblems and then solved just like in Merge Sort or Quick Sort.
Though I am not posting this question to get my assignment solved by you people , Our professor gave us an assignment to implement Bubble Sort as a divide and conquer algorithm , Now I'm sitting on my laptop scratching my head for days on how Bubble Sort can be divide and conquer algorithm.
If I try to implement Bubble Sort as divide and conquer the array must be divided , when I divide the array into its last element and then merge it back to its sorted form , The algorithm just becomes Merge Sort.
If I implement it by recursively calling bubbleSort(array,size1) , the algorithm becomes Reduce and Conquer.
My question is "How can bubble sort be implemented as Divide and Conquer Algorithm ?"

1a quick google turns up cs.iusb.edu/~danav/teach/b424/b424_15_bubblesort.html cpp.edu/~gsyoung/CS370/14Sp/parallel_sorting_kla%20Danny.pdf– Alan BirtlesApr 10 '20 at 15:20

3imo, you are correct. Merge sort is but the divide and conquer approach over bubble sort(which by itself is an iterative algo). Perhaps your Prof played a trick question on you.– theWiseBroApr 10 '20 at 15:25

Given the Bubble Sort Algorithm and its complexity as O(n2), convert it into Divide & Conquer Algorithm and calculate its time complexity.– Waqas TahirApr 10 '20 at 15:45

1Suppose you just wrote a regular bubble sort algorithm, and then used that in place of the merge helper in merge sort.– Kenny OstromApr 10 '20 at 15:45

1No way. How do I know you already wrote your own bubblesort, or your own merge sort? :)– Kenny OstromApr 10 '20 at 15:55
Assume you write a bubblesort
function that lets you sort part of an array:
bubblesort(arr, start, end)
{
// sorts the items from arr[start] to arr[end]
}
So if you had the array [1,7,4,9,6,3,2,5]
and called bubblesort(arr, 0, 3)
, the resulting array would be [1,4,7,9,6,3,2,5]
.
Now imagine what would happen if you made these calls:
bubblesort(arr, 0, 1);
bubblesort(arr, 2, 3);
bubblesort(arr, 4, 5);
bubblesort(arr, 6, 7);
Then
bubblesort(arr, 1, 3);
bubblesort(arr, 4, 7);
And, finally:
bubblesort(arr, 0, 7);
It's the same call pattern as merge sort, but it's definitely not merge sort.


1@WaqasTahir The first problem is that your
bubbleSort
method doesn't work. Fix that first. Then, rethink what yourmergeSort
is doing. Give it some thought, singlestep your code in the debugger. If you still have trouble, post a new question that explains what you're trying to do, include your code, and describe the problem you're having. Apr 11 '20 at 16:01 

@WaqasTahir Time complexity of this divideandconquer bubble sort? O(n^2). Apr 12 '20 at 3:57