______ sorting algorithm does not have a worst case running time O(n 2 ) .

To determine which sorting algorithm does not have a worst-case running time of O(n^2), we analyze the time complexity of each algorithm: 1. Insertion Sort: In the worst case (reverse sorted array), it takes O(n^2) time because each element must be compared and moved to its correct position. 2. Merge Sort: It uses a divide-and-conquer approach, splitting the array into halves recursively. The merging step takes O(n) time, and the depth of recursion is O(log n). Hence, the worst-case time complexity is O(n log n). 3. Quick Sort: In the worst case (e.g., already sorted array with first element as pivot), it results in unbalanced partitions, leading to O(n^2) time complexity. 4. Bubble Sort: It compares adjacent elements and swaps them if out of order. In the worst case, it requires O(n^2) comparisons and swaps. Therefore, the only algorithm among the options that does not have a worst-case time complexity of O(n^2) is Merge Sort.