155. OCR A Level (H446) SLR26 – 2.3 Implement merge sort

What principle does the merge sort algorithm use?

• Greedy method

• Backtracking

• Dynamic programming

• Divide and conquer

Answer explanation

The merge sort algorithm uses the principle of divide and conquer to recursively divide the array into smaller subarrays, sort them, and then merge them back together.

What is the first step in implementing a merge sort?

• Sorting the entire dataset

• Putting each item in its own list

• Merging two lists

• Splitting the dataset in half

Answer explanation

The first step in implementing a merge sort is putting each item in its own list, before proceeding to merge and sort the lists.

What environment is merge sort ideal for?

• Single-threaded applications

• Low memory usage

• Parallel processing

• Sequential processing

Answer explanation

Merge sort is ideal for parallel processing due to its ability to efficiently divide the workload among multiple processors or cores.

What is the main advantage of using lists in a merge sort?

• Fixed size

• Faster access time

• Simpler code

• Easy deletion operation

Answer explanation

The main advantage of using lists in a merge sort is the easy deletion operation, which allows for efficient removal of elements during the sorting process.

How many lists does the merge function take as input?

• One

• Two

• Three

• Four

Answer explanation

The merge function takes two lists as input to combine them into a single list, so the correct answer is Two.

What does the merge function return?

• A boolean value

• A single sorted list

• Two sorted lists

• The original lists unmodified

Answer explanation

The merge function returns a single sorted list, combining and sorting the elements from the input lists.

What is used to track the position in the lists inside the merge function?

• Flags

• Pointers

• Counters

• Index variables

Answer explanation

Index variables are used to track the position in the lists inside the merge function.

What happens to the local variables of the merge function after it returns?

• They are reset

• They are deleted

• They lose scope and cease to exist

• They are stored for later use

Answer explanation

The local variables of the merge function lose scope and cease to exist after it returns, as they are stored on the stack and are popped off when the function completes.

What is the condition to enter the outer while loop in the merge sort algorithm?

• The list of items contains more than one list

• The list of items contains exactly one list

• The list of items is empty

• The list of items is sorted

Answer explanation

The condition to enter the outer while loop in the merge sort algorithm is that the list of items contains more than one list.

What does the merge sort algorithm do with the original unsorted list?

• Duplicates it

• Sorts it in place

• Deletes it

• Splits it into single-item lists

Answer explanation

Merge sort algorithm splits the original unsorted list into single-item lists before sorting them recursively.