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,size-1) , the algorithm becomes Reduce and Conquer.

My question is "How can bubble sort be implemented as Divide and Conquer Algorithm ?"

  • 1
  • 3
    imo, 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.
    – theWiseBro
    Apr 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. Apr 10 '20 at 15:45
  • 1
    Suppose you just wrote a regular bubble sort algorithm, and then used that in place of the merge helper in merge sort. Apr 10 '20 at 15:45
  • 1
    No way. How do I know you already wrote your own bubblesort, or your own merge sort? :) Apr 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);


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.

  • but still does not work , can you please guide me on what's wrong Apr 11 '20 at 15:23
  • 1
    @WaqasTahir The first problem is that your bubbleSort method doesn't work. Fix that first. Then, re-think what your mergeSort is doing. Give it some thought, single-step 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
  • What's the time complexity Apr 11 '20 at 23:26
  • @WaqasTahir Time complexity of this divide-and-conquer bubble sort? O(n^2). Apr 12 '20 at 3:57

Your Answer

