Sort a Linked List Using Merge Sort in DSA C - 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, sorts each half recursively, 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, while quicksort needs random access which linked lists do not support efficiently.

beginner

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

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.

beginner

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

The base case is when the linked list is empty or has only one node, which means it is already sorted.

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

A Two pointers: slow and fast

B Counting nodes and dividing by two

C Using an array to store nodes

D Randomly splitting the list

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

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

A Swapping nodes randomly

B Deleting duplicates

C Reversing the list

D Merging the two sorted halves

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

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

A O(n^2)

B O(n)

C O(n log n)

D O(log n)

Merge sort has a time complexity of O(n log n) for linked lists.

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

A Because merge sort uses random access

B Because merge sort merges lists without random access

C Because quicksort is not recursive

D Because quicksort uses extra memory

Merge sort merges sorted lists efficiently without needing random access, which linked lists do not support well.

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

A List is empty or has one node

B List has two nodes

C List has more than ten nodes

D List is sorted

The base case is when the list is empty or has only one node, meaning it is already sorted.

Explain step-by-step how merge sort works on a linked list.

Think about dividing the list and combining sorted parts.

Describe why merge sort is a good choice for sorting linked lists compared to other sorting algorithms.

Consider linked list properties and algorithm behavior.