A general-purpose, comparison-based sorting algorithm that divides input into smaller parts, sorts them, and merges the sorted parts.

What are the three divide-and-conquer stages?

Divide the input, conquer by solving the smaller subproblems, and combine their results.

Why is a one-element list a base case?

It is sorted by definition, so recursive division can stop at that point.

How does the merge step work?

It repeatedly compares the first remaining elements of two sorted inputs, outputs the smaller one, and finally appends whichever input remains.

Define a stable sort.

A stable sort preserves the input order of elements that have equal keys. Merge sort is usually stable when its merge step handles ties appropriately.

Data structures & algorithmsLesson 1 of 1 in the course Algorithm analysis and sorting

Merge Sort: Algorithms, Complexity, Variants, and Applications

5 flashcards · 5 quiz questions · 5 match pairs · 4 fill-in sentences · English

Save course

Lesson progress

0 / 5

Your progress is kept in this browser only.Sign up to save it

Summary

Merge sort is a general-purpose comparison-based sorting algorithm. This lesson introduces its divide-and-conquer strategy and explains why merging sorted sequences is the key to its efficiency.

A list of zero or one elements is already sorted. Therefore, dividing continues until the sublists each contain at most one element. These tiny sorted sublists are then merged in stages.

All flashcards

What is merge sort?: A general-purpose, comparison-based sorting algorithm that divides input into smaller parts, sorts them, and merges the sorted parts.
What are the three divide-and-conquer stages?: Divide the input, conquer by solving the smaller subproblems, and combine their results.
Why is a one-element list a base case?: It is sorted by definition, so recursive division can stop at that point.
How does the merge step work?: It repeatedly compares the first remaining elements of two sorted inputs, outputs the smaller one, and finally appends whichever input remains.
Define a stable sort.: A stable sort preserves the input order of elements that have equal keys. Merge sort is usually stable when its merge step handles ties appropriately.

Quiz questions

For merge sort on an input of size n, what time complexity follows from $T(n)=2T(n/2)+n$ ?Answer: $O(n \log n)$
How much auxiliary memory does the common array-based merge sort implementation use?Answer: $O(n)$ extra memory
What makes external merge sort suitable for data that cannot fit in main memory?Answer: It sorts manageable runs and merges them using sequential storage access.
Why is merge sort well suited to linked lists?Answer: Sorted parts can be merged by relinking nodes without fast random access.
In parallel merge sort, why might the merge stage be parallelized?Answer: A sequential merge can limit the parallelism gained from sorting halves concurrently.

Based on the Wikipedia article Merge sort, licensed CC BY-SA 4.0. Adapted into a summary, flashcards and quizzes.

All Data structures & algorithms lessons

Data structures & algorithmsBinary Heaps: Ordering, Array Operations, and Applications5 flashcards · 5 quiz questions · 4 gamesPlay free →Data structures & algorithmsBinary Search Trees: Ordering, Operations, Height, and Uses5 flashcards · 5 quiz questions · 4 gamesPlay free →

Summary

All flashcards

Quiz questions

More in Data structures & algorithms