Course- BTech Type- Core
Course Code- CSET243 Course Name- Data Structures using C++
Year- Second rd
Semester- Odd Batch- BTech 3 Semester
Tutorial No. Name CO1 CO2 CO3
1 Bubble, Insertion, -- --
Selection, and
Merge Sort
Objective: The main objective of this tutorial is to learn about sorting algorithms Bubble,
Insertion, Selection, and Merge Sort.
Tutorial 5
[Link] is NOT true about Merge Sort?
a) Always O(n log n)
b) Requires O(n) extra space
c) Stable sorting algorithm
d) In-place sorting
• Answer: d) In-place sorting
• Explanation: Merge Sort is a stable, O(n log n) sorting algorithm. It requires O(n) extra
space for the temporary array used during the merge step, making it not an in-place sorting
algorithm.
A sorting algorithm is in-place if it requires only a small, constant amount of extra memory
O(1) in addition to the input array.
Examples: Insertion sort, Bubble sort, Selection sort.
Merge sort is not in-place because it requires O(n) extra memory for merging subarrays,
unlike in-place algorithms that use only constant extra memory.
Why Merge Sort is not in-place
During the merge operation, we cannot overwrite elements in the original array
safely, since we need to compare and place them in order.
Therefore, an auxiliary array is used to store merged elements before copying them
back.
This means merge sort has a space complexity of O(n), not O(1).
Hence, merge sort is not an in-place sorting algorithm.
[Link] Bubble Sort, after k passes, how many of the largest elements are guaranteed to be in
their final position?
a) k
b) n-k
c) log₂k
d) None
Answer: a)k
[Link] sorting algorithm is a divide and conquer algorithm?
a) Bubble Sort
b) Insertion Sort
c) Selection Sort
d) Merge Sort
Answer: d) Merge Sort
Explanation: Merge Sort is a classic example of a divide and conquer algorithm. It divides
the unsorted list into two sub-lists, recursively sorts them, and then merges them back
together to create a sorted list.
[Link] the input size is doubled, the running time of Merge Sort increases by approximately:
A) 2 times
B) 4 times
C) (nlogn) times
D) Between 2 and 4
Answer: D) Between 2 and 4
Explanation: Merge Sort's time complexity is O(n log n). If the input size n is doubled to 2n,
the new running time is approximately 2n * log(2n) = 2n * (log 2 + log n) =
2n * log n + 2n * 1. This is more than double the original time but less than four
times, placing the increase between 2 and 4.
[Link] of the following correctly describes the space complexity of Merge Sort vs Insertion
Sort?
A) Merge Sort: O(1), Insertion Sort: O(n)
B) Merge Sort: O(n), Insertion Sort: O(1)
C) Merge Sort: O(logn), Insertion Sort: O(n)
D) Both have O(n) auxiliary space
Answer: B) Merge Sort: O(n), Insertion Sort: O(1)
Explanation: Merge Sort requires an auxiliary array of size O(n) for its merge step, making
its space complexity O(n). Insertion Sort is an in-place algorithm that only uses a few
temporary variables for comparisons and swaps, giving it a space complexity of O(1).
[Link] array of size n is sorted using Insertion Sort.
If exactly k inversions are present in the array, the time complexity becomes:
a) O(k)
b) O(n + k)
c) O(n log k)
d) O(n²)
• Answer: b) O(n + k)
• Explanation: The time complexity of Insertion Sort depends on the number of inversions
in the array. In the best case (a sorted array with k=0 inversions), it is O(n). In the worst case
(a reverse-sorted array with k = n(n-1)/2 inversions), it is O(n²). The time complexity can be
precisely described as O(n + k).
[Link] the primary trade-offs between using a linked list and a dynamic array to store a
collection of elements. Under what specific circumstances would you choose one over the
other?
• Answer: The primary trade-off is between random access and efficient
insertions/deletions.
•Linked lists are excellent for operations like insertion and deletion, which can be done in
O(1) time if you have a pointer to the correct location. However, they are poor for random
access, requiring O(n) time to find the n-th element. They also use more memory due to the
overhead of storing pointers.
•Dynamic arrays provide O(1) time for random access but are inefficient for insertions and
deletions in the middle, which can take O(n) time due to the need to shift elements.
• Choice: Choose a linked list when your program performs frequent insertions or deletions
and does not require fast access to random elements. Choose a dynamic array when you
need fast random access and insertions/deletions are less frequent or occur primarily at the
end.
8. Bubble Sort Edge Case Analysis
Prove that if Bubble Sort is implemented with a flag that checks whether any swaps occurred
in a pass, the best-case time complexity reduces from O(n^2) to O(n). Explain why this
modification has no impact on the worst-case complexity.
Answer: If Bubble Sort is implemented with a flag that checks if any swaps occurred in a
pass, the best-case time complexity becomes O(n). In an already sorted array, the first pass
will complete n-1 comparisons without performing any swaps. The flag will remain false,
causing the loop to terminate after the first pass. The complexity is thus linear, or O(n).
Explanation: This modification has no impact on the worst-case complexity. In a
reverse-sorted array, a swap will occur in every inner loop iteration of every pass. The flag
will always be true, so the algorithm will not terminate early and will proceed through all n-
1 passes, resulting in a worst-case time complexity of O(n²).
9. Consider an array of n elements where half the elements are already sorted, and the other
half are in random order.
•Compare the performance of Bubble Sort, Insertion Sort, and Merge Sort for this scenario.
•Which algorithm benefits most from this input, and why?
Explanation:
● Insertion Sort: Its performance depends on the number of inversions. With half the
array sorted, the number of inversions is significantly reduced compared to a fully
random array. It will perform close to its best-case O(n) and far better than its worst-
case O(n²).
● Bubble Sort: Although the number of passes might decrease in an optimized
version, it will still have to perform a high number of comparisons and swaps to move
the randomly ordered elements into their correct positions. Its complexity would be
somewhere between O(n) and O(n²), but likely closer to the latter.
● Merge Sort: Its time complexity is consistently O(n log n) regardless of the initial
order of the data. It does not benefit from the partial sorting and will always perform
the same number of merge operations.
10. Given an array with repeated elements, analyze how stability impacts the correctness of
sorting in real-world applications (e.g., sorting employees by salary and then by name).
Answer: Stability in sorting means that the relative order of equal elements is preserved
after sorting. In real-world applications with repeated elements (e.g., records in a database),
stability is crucial for maintaining a secondary sort order.
Explanation: Consider sorting employees by salary (primary key) and then by name
(secondary key). If you first sort the list by name, a stable sort by salary will group
employees with the same salary together while maintaining their original name-based
order. If an unstable sort (like Selection Sort) were used, the relative order of employees
with the same salary could be rearranged, destroying the prior name-based sort.
11. An e-commerce company receives two sorted lists of order amounts:
• List A: [120, 250, 400, 550]
• List B: [100, 300, 450, 600]
Explain how Merge Sort merges these two lists into a single sorted list, step by step, and
mention why this method is efficient for large datasets.
Answer: Merge Sort is highly efficient for merging two sorted lists. This is a primary step in
the "merge" phase of the algorithm.
Step-by-step merge process:
1. Initialize a new empty list and two pointers, one at the beginning of List A (120) and
one at the beginning of List B (100).
2. Compare the current elements: 100 < 120. Append 100 to the new list and move
the pointer in List B. New list: [100].
3. Compare 120 and 300. Append 120 and move the pointer in List A. New list: [100,
120].
4. Compare 250 and 300. Append 250 and move the pointer in List A. New list: [100,
120, 250].
5. Compare 400 and 300. Append 300 and move the pointer in List B. New list: [100,
120, 250, 300].
6. Continue this process until one list is exhausted.
7. Append the remaining elements from the other list to the new list.
Efficiency: This merge process is very efficient because it only requires a single pass over
the elements of both lists, resulting in an O(n) time complexity. For large datasets, this linear
time merge is a key reason Merge Sort's overall O(n log n) complexity is so robust.