Sorting algorithms: bubble, insertion and merge

9.Which sorting algorithm is generally considered the most efficient for large datasets due to its O(n log n) time complexity?

10.A sorting algorithm must produce an output where each element is in monotonic order and the output is a permutation of the input.

11.Which sorting algorithm is described as an 'online' algorithm because it can sort a constant stream of input as it arrives?

12.Which of the following are characteristics of a stable sorting algorithm? (Select all that apply)

13.Match each sorting algorithm with its general method classification.

14.Arrange the steps of one pass of bubble sort on the list [5, 2, 4, 1] in the correct order.

15.Merge sort is typically recursive and has a worst-case time complexity of O(n log n).

16.Which sorting algorithm would you choose if you need a stable sort with O(n log n) worst-case time complexity?

17.Which of the following are true about the number of comparisons in bubble sort on a list of n elements? (Select all that apply)

18.A list of student names is sorted alphabetically using bubble sort. In the first pass, how many comparisons are made if the list contains 8 names?

19.A list of numbers is [3, 1, 4, 2]. After one complete pass of bubble sort (largest element bubbling to the end), what is the resulting list?

20.Insertion sort is used to sort the list [5, 2, 4, 1]. After the first two elements have been processed (i.e., after inserting the second element), what is the list?

21.Which of the following statements are true about the number of comparisons and swaps in bubble sort on a list of n elements? (Select all that apply)

22.Insertion sort is generally more efficient than bubble sort for nearly sorted lists because it can stop early when elements are in place.

23.Match each sorting algorithm with its typical time complexity in the worst case.

24.Arrange the following steps in the correct order for one pass of bubble sort on the list [4, 3, 2, 1].

25.A list of numbers is [10, 9, 8, 7, 6]. Using insertion sort, how many comparisons are made in total to sort the list?

26.A student is using bubble sort on a list of 6 numbers. After the first full pass, the largest number is guaranteed to be in its correct position. How many comparisons are made in the first pass?

27.Which sorting algorithm uses a 'divide and conquer' approach by recursively splitting the list into smaller sublists, sorting them, and then merging them back together?

28.Insertion sort is more efficient than bubble sort on a nearly sorted list because it can stop early when elements are in place.

29.Which of the following are true about the time complexity of the sorting algorithms? (Select all that apply)

30.When using merge sort to sort a list of 16 numbers, how many levels of splitting are needed until each sublist contains only one element?

31.Match each sorting algorithm with its typical worst-case time complexity.

32.A list of student records is first sorted by name using a stable sort, then sorted by class section using the same stable sort. What is the result regarding the order of students within the same class section?

33.A sorting algorithm must reorder the input list so that each element is in the correct order, and the output must contain all the original elements.

34.Which of the following is the correct order of steps for one pass of bubble sort on the list [4, 3, 2, 1]?

35.Which of the following are true about insertion sort? (Select all that apply)

36.Merge sort is typically implemented recursively and has a worst-case time complexity of O(n log n).

37.Which of the following is NOT a characteristic of bubble sort?

38.Match each sorting algorithm to its general method classification.

39.Arrange the steps of one complete pass of bubble sort on the list [5, 2, 4, 1] in the correct order (the pass ends when the largest element is at the end).

40.Which of the following statements about insertion sort are true? (Select all that apply)

41.Complete the sentence:

42.How many comparisons are made in the first pass of bubble sort on a list of 5 elements?

43.What does it mean for a sorting algorithm to be 'stable'?

44.Complete the sentence about sorting algorithms.

45.What is the term for a sorting algorithm that requires only O(1) extra memory beyond the items being sorted?

46.Merge sort divides a list of 64 items into two halves, then sorts each half recursively. How many levels of splitting are needed until each sublist contains only one item?

47.Complete the sentence about the time complexity of merge sort.

48.A bubble sort makes a pass through a list of n elements, comparing adjacent pairs. How many comparisons are made in the first pass?

49.Which sorting algorithm is an 'online' algorithm, meaning it can sort a constant stream of input as it arrives?

50.Complete the sentence about the number of passes in bubble sort.

51.Complete the sentence about merge sort's approach.

52.A list of 8 numbers is sorted using insertion sort. In the worst case, how many comparisons are made in total?

53.Explain why stability is important when sorting student records first by name and then by class section.

54.Describe how merge sort uses the divide-and-conquer approach to sort a list, and explain why it is more efficient than bubble sort for large lists.

55.Explain the difference between a stable and an unstable sorting algorithm, and give one example of each from the list: bubble sort, insertion sort, merge sort.

56.Explain why merge sort is generally more efficient than bubble sort for large lists, and describe the trade-off in memory usage.

57.How many comparisons are made in the first pass of bubble sort on a list of 5 elements?

58.Merge sort divides a list of 64 items into two halves, then sorts each half recursively. How many levels of splitting are needed until each sublist contains only one item?

59.A bubble sort makes a pass through a list of n elements, comparing adjacent pairs. How many comparisons are made in the first pass?

60.A list of 8 numbers is sorted using insertion sort. In the worst case, how many comparisons are made in total?