Divide And Conquer Bubble Sort Algorithm

Question

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 ?"

a 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 Birtles
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
Given the Bubble Sort Algorithm and its complexity as O(n2), convert it into Divide & Conquer Algorithm and calculate its time complexity. — Waqas Tahir
Suppose you just wrote a regular bubble sort algorithm, and then used that in place of the merge helper in merge sort. — Kenny Ostrom
No way. How do I know you already wrote your own bubblesort, or your own merge sort? :) — Kenny Ostrom

Jim Mischel Jim Mischel · Accepted Answer · 2020-04-10T23:30:50

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.

Divide And Conquer Bubble Sort Algorithm

1 Answers