1.1.12

Merge Sort

Test yourself on Merge Sort

Test your knowledge with free interactive questions on Seneca — used by over 10 million students.

Merge Sort

Merge sort is an example of a divide and conquer algorithm, where the problem is broken down into smaller steps.

The concept

The concept

If we have two packs of cards, which are both already in order and want to combine them, what can we do?
One solution is to only consider the top card of each pile, and create a new deck starting from the smaller of the two cards.
This will give us a combined sorted pack.
This is called merge sort.

In English

In English

Split the lists into lists of size one.
Merge each pair of sublists by comparing the first value of each list and putting the smaller value into the new list first.
Continue merging until there is only one list.

Pros and cons of merge sort:

Pros and cons of merge sort:

Pros:
- A very efficient algorithm.
Cons:
- Can be slower for small lists.
- Needs additional memory.

Merge Sort

Merge sort is an example of a divide-and-conquer algorithm, where the problem is broken down into smaller steps.

The concept in the context of cards

The concept in the context of cards

If we have two packs of cards, which are both already in order and want to combine them, what can we do?
One solution is to only consider the top card of each pile, and create a new deck starting from the smaller of the two cards.
This will give us a combined sorted pack.
This is called merge sort.

The process

The process

Split the lists into lists of size one.
Merge each pair of sublists by comparing the first value of each list and putting the smaller value into the new list first.
Continue merging until there is only one list.

Pros and cons of merge sort

Pros and cons of merge sort

Pros:
- A very efficient algorithm.
Cons:
- Can be slower for small lists.
- Needs additional memory.

1

Problem Solving

1.1

Algorithms

1.1.1Algorithm Thinking 1.1.2Interpreting Algorithms 1.1.3Expressing Algorithms - Pseudocode 1.1.4Expressing Algorithms - Flow Charts 1.1.5Correcting Algorithms 1.1.6Completing Algorithms 1.1.7Search Algorithms 1.1.8Linear Search 1.1.9Binary Search 1.1.10Sort Algorithms 1.1.11Bubble Sort 1.1.12Merge Sort

1.2

Decomposition & Abstraction

1.2.1Computational Thinking - Abstraction 1.2.2Computational Thinking - Decomposition 1.2.3End of Topic Test - Algorithms

2

Programming

3

Data

3.1

Binary

3.1.1Number Bases 3.1.2Negative Binary Numbers 3.1.3Binary Addition 3.1.4Binary Shifts

3.2

Data Representation

3.2.1Representing Text 3.2.2ASCII 3.2.3Unicode 3.2.4Representing Images 3.2.5Representing Sound

3.3

Data Storage & Compression

3.3.1Capacity 3.3.2Calculating Capacity Requirements 3.3.3Data Compression 3.3.4Run Length Encoding

3.4

Encryption

3.4.1Encryption 3.4.2Caesar Cipher 3.4.3Ciphers

3.5

Databases

3.5.1Databases 3.5.2End of Topic Test - Data & Representation

4

Computers

4.1

Machines & Computational Modelling

4.1.1Computational Models 4.1.2Input-Process-Output Model

4.2

Hardware

4.3

Logic

4.3.1Binary Systems 4.3.2Logic Circuits 4.3.3Boolean Logic 4.3.4End of Topic Test - Logic

4.4

Software

4.4.1Operating Systems 4.4.2User Interface Managetment 4.4.3Memory and Process Management 4.4.4File Management 4.4.5Device Management 4.4.6User Management 4.4.7Encryption Software 4.4.8Defragmentation Software 4.4.9Data Compression Software 4.4.10Backup Software

4.5

Programming Languages

4.5.1High Level Languages 4.5.2Low Level Languages 4.5.3Translators - Compilers 4.5.4Translators - Interpreters 4.5.5Translators - Assemblers 4.5.6End of Topic Test - Translation & Representation

5

Communication & The Internet

5.1

Networks

5.2

Network Security

5.2.1User Access Levels 5.2.2Encryption 5.2.3Protecting Against Malware 5.2.4Firewalls 5.2.5Forms of Attack 5.2.6Penetration Testing 5.2.7Malware 5.2.8How Malware Spreads 5.2.9Social Engineering 5.2.10Protecting Against Social Engineering 5.2.11Phishing 5.2.12Network Administration 5.2.13Network Forensics

5.3

The Internet & the World Wide Web

5.3.1IP Addresses 5.3.2Types of IP Address 5.3.3MAC Addresses 5.3.4Packet Switching 5.3.5How Do Packets Get Routed?5.3.6Did My Data Arrive Safely?5.3.7The Internet 5.3.8URLs 5.3.9DNS 5.3.10Web Hosting 5.3.11End of Topic Test - Security

6

The Bigger Picture

Jump to other topics

1

Problem Solving

1.1

Algorithms

1.1.1Algorithm Thinking 1.1.2Interpreting Algorithms 1.1.3Expressing Algorithms - Pseudocode 1.1.4Expressing Algorithms - Flow Charts 1.1.5Correcting Algorithms 1.1.6Completing Algorithms 1.1.7Search Algorithms 1.1.8Linear Search 1.1.9Binary Search 1.1.10Sort Algorithms 1.1.11Bubble Sort 1.1.12Merge Sort

1.2

Decomposition & Abstraction

1.2.1Computational Thinking - Abstraction 1.2.2Computational Thinking - Decomposition 1.2.3End of Topic Test - Algorithms

2

Programming

3

Data

3.1

Binary

3.1.1Number Bases 3.1.2Negative Binary Numbers 3.1.3Binary Addition 3.1.4Binary Shifts

3.2

Data Representation

3.2.1Representing Text 3.2.2ASCII 3.2.3Unicode 3.2.4Representing Images 3.2.5Representing Sound

3.3

Data Storage & Compression

3.3.1Capacity 3.3.2Calculating Capacity Requirements 3.3.3Data Compression 3.3.4Run Length Encoding

3.4

Encryption

3.4.1Encryption 3.4.2Caesar Cipher 3.4.3Ciphers

3.5

Databases

3.5.1Databases 3.5.2End of Topic Test - Data & Representation

4

Computers

4.1

Machines & Computational Modelling

4.1.1Computational Models 4.1.2Input-Process-Output Model

4.2

Hardware

4.3

Logic

4.3.1Binary Systems 4.3.2Logic Circuits 4.3.3Boolean Logic 4.3.4End of Topic Test - Logic

4.4

Software

4.4.1Operating Systems 4.4.2User Interface Managetment 4.4.3Memory and Process Management 4.4.4File Management 4.4.5Device Management 4.4.6User Management 4.4.7Encryption Software 4.4.8Defragmentation Software 4.4.9Data Compression Software 4.4.10Backup Software

4.5

Programming Languages

4.5.1High Level Languages 4.5.2Low Level Languages 4.5.3Translators - Compilers 4.5.4Translators - Interpreters 4.5.5Translators - Assemblers 4.5.6End of Topic Test - Translation & Representation

5

Communication & The Internet

5.1

Networks

5.2

Network Security

5.2.1User Access Levels 5.2.2Encryption 5.2.3Protecting Against Malware 5.2.4Firewalls 5.2.5Forms of Attack 5.2.6Penetration Testing 5.2.7Malware 5.2.8How Malware Spreads 5.2.9Social Engineering 5.2.10Protecting Against Social Engineering 5.2.11Phishing 5.2.12Network Administration 5.2.13Network Forensics

5.3

The Internet & the World Wide Web

5.3.1IP Addresses 5.3.2Types of IP Address 5.3.3MAC Addresses 5.3.4Packet Switching 5.3.5How Do Packets Get Routed?5.3.6Did My Data Arrive Safely?5.3.7The Internet 5.3.8URLs 5.3.9DNS 5.3.10Web Hosting 5.3.11End of Topic Test - Security

6

The Bigger Picture

Practice questions on Merge Sort

Can you answer these? Test yourself with free interactive practice on Seneca — used by over 10 million students.

1
When is it a particularly **bad** idea to use merge sort?Multiple choice
2
Merge Sort in EnglishPut in order
3
Merge SortPut in order
4
What are the potential drawbacks of using merge sort?Fill in the list
5
A list of 5 elements needs to be sorted. Which is the most appropriate algorithm?Multiple choice

Answer all questions on Merge Sort

Unlock your full potential with Seneca Premium

Unlimited access to 10,000+ open-ended exam questions
Mini-mock exams based on your study history
Unlock 800+ premium courses & e-books

Get started with Seneca Premium

Bubble Sort

Computational Thinking - Abstraction