Solution

Solution

Bubble Sort repeatedly steps through the list, comparing adjacent elements and swapping them if they are in the wrong order, until the list is sorted.

Process:

• Start from the beginning of the list.
• Compare each pair of adjacent elements.
• Swap them if they are in the wrong order.
• Continue until no more swaps are needed.

Example: For $[5,3,8,4,2]$, Bubble Sort first compares $5$ and $3$ and swaps them, then compares the next pair ($5$ and $8$), and so on. After several passes the list becomes $[2,3,4,5,8]$.

Time complexity: $O(n^{2})$. This makes Bubble Sort inefficient for large datasets. It is easy to understand and implement, so it is useful for teaching and for small lists.

Comparison with Merge Sort

Merge Sort uses divide and conquer: the list is split into smaller parts, each part is sorted, and the sorted parts are combined. Its time complexity is $O(n \log n)$, a polynomial (tractable) bound. Sorting with Merge Sort or Quick Sort is treated as efficiently solvable in this chapter.

For larger datasets, more efficient algorithms such as Merge Sort or Quick Sort save time and resources.