Sort a Linked List Using Merge Sort in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind merge sort when sorting a linked list?

Merge sort divides the linked list into two halves, recursively sorts each half, and then merges the two sorted halves back together.

intermediate

Why is merge sort preferred over quicksort for sorting linked lists?

Merge sort works well with linked lists because it does not require random access and can merge two sorted lists efficiently by changing pointers, while quicksort relies on random access which linked lists do not support efficiently.

beginner

How do you find the middle of a linked list efficiently?

Use two pointers: a slow pointer that moves one step at a time and a fast pointer that moves two steps at a time. When the fast pointer reaches the end, the slow pointer will be at the middle.

beginner

What is the time complexity of merge sort on a linked list?

The time complexity is O(n log n), where n is the number of nodes in the linked list.

intermediate

What is the space complexity of merge sort on a linked list?

The space complexity is O(log n) due to the recursion stack used during the divide steps.

Which technique is used to split the linked list into two halves in merge sort?

A Randomly splitting the list

B Two pointers: slow and fast

C Using a stack to store nodes

D Counting nodes and dividing by two

Two pointers, slow and fast, are used to find the middle efficiently without counting all nodes.

What is the main operation performed after recursively sorting the two halves in merge sort?

A Swapping nodes randomly

B Reversing the list

C Merging the two sorted halves

D Deleting duplicate nodes

After sorting each half, merge sort merges the two sorted halves into one sorted list.

Why is merge sort efficient for linked lists compared to quicksort?

A Because merge sort uses pointer manipulation without random access

B Because quicksort is not a sorting algorithm

C Because merge sort uses extra arrays

D Because quicksort requires recursion

Merge sort efficiently merges by changing pointers, while quicksort needs random access which linked lists lack.

What is the base case for the recursive merge sort on a linked list?

A When the list is fully sorted

B When the list has two nodes

C When the list has more than ten nodes

D When the list is empty or has only one node

A list with zero or one node is already sorted, so recursion stops there.

What is the output format after sorting a linked list using merge sort?

A A sorted linked list with nodes connected in ascending order

B An array of sorted values

C A reversed linked list

D A list of unsorted nodes

The output is a linked list sorted in ascending order, with nodes connected properly.

Explain step-by-step how merge sort sorts a linked list.

Think about dividing and conquering the list.

Describe how merging two sorted linked lists works in merge sort.

Imagine merging two sorted lines of people by height.