1.1.12

Merge Sort

Test yourself

Merge Sort

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

Illustrative background for The conceptIllustrative background for The concept ?? "content

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.
Illustrative background for In EnglishIllustrative background for In English ?? "content

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.
Illustrative background for Pros and cons of merge sort:Illustrative background for Pros and cons of merge sort: ?? "content

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.

Illustrative background for The concept in the context of cardsIllustrative background for The concept in the context of cards ?? "content

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.
Illustrative background for The processIllustrative background for The process ?? "content

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.
Illustrative background for Pros and cons of merge sortIllustrative background for Pros and cons of merge sort ?? "content

Pros and cons of merge sort

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

Jump to other topics

1Problem Solving

1.1Algorithms

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.2Decomposition & Abstraction

1.2.1Computational Thinking - Abstraction

1.2.2Computational Thinking - Decomposition

1.2.3End of Topic Test - Algorithms

2Programming

2.1Develop Code

2.1.1Maintainability

2.1.2Comments

2.1.3Exceptions

2.1.4Syntax Error

2.1.5Logic Error

2.1.6Runtime Error

2.1.7Purpose of Testing

2.1.8Test Plans

2.2Constructs

2.2.1Selection

2.2.2Sequence

2.2.3Iteration

2.3Data Types & Structures

2.3.1Variables & Constants

2.3.2Scope

2.3.3Data Types

2.3.4Casting

2.3.5Data Structures - Arrays

2.3.6Data Structures - 2D Arrays

2.3.7Data Structures - Strings

2.3.8Data Structures - Records

2.4Input / Output

2.4.1Input and Output

2.4.2Validation and Sanitation

2.4.3Files

2.4.4File Handling

2.5Operators

2.5.1Arithmetic Operators

2.5.2Relational Operators

2.5.3Boolean Operators

2.6Subprograms

2.6.1Modularity

2.6.2End of Topic Test - Programming

3Data

3.1Binary

3.1.1Number Bases

3.1.2Negative Binary Numbers

3.1.3Binary Addition

3.1.4Binary Shifts

3.2Data Representation

3.2.1Representing Text

3.2.2ASCII

3.2.3Unicode

3.2.4Representing Images

3.2.5Representing Sound

3.3Data Storage & Compression

3.3.1Capacity

3.3.2Calculating Capacity Requirements

3.3.3Data Compression

3.3.4Run Length Encoding

3.4Encryption

3.4.1Encryption

3.4.2Caesar Cipher

3.4.3Ciphers

3.5Databases

3.5.1Databases

3.5.2End of Topic Test - Data & Representation

4Computers

4.1Machines & Computational Modelling

4.1.1Computational Models

4.1.2Input-Process-Output Model

4.2Hardware

4.2.1Elements of Computer Systems

4.2.2Types of Computer Systems

4.2.3Memory - RAM

4.2.4Memory - ROM

4.2.5Memory - Cache

4.2.6Running Out of Memory

4.2.7Virtual Memory

4.2.8Magnetic Storage

4.2.9Properties of Magnetic Media

4.2.10Examples of Magnetic Storage

4.2.11Solid State Storage

4.2.12Properties of Solid State Media

4.2.13Optical Storage

4.2.14Properties of Optical Storage

4.2.15Examples of Optical Storage

4.2.16Types of Optical Disk

4.2.17Von Neumann Architecture

4.2.18Registers of the Central Processing Unit (CPU)

4.2.19Fetch-Decode-Execute Cycle

4.2.20Factors Affecting CPU Performance

4.2.21The Cloud

4.2.22How the Cloud Works

4.2.23The Cloud - Pros

4.2.24The Cloud - Cons

4.2.25End of Topic Test - Hardware

4.3Logic

4.3.1Binary Systems

4.3.2Logic Circuits

4.3.3Boolean Logic

4.3.4End of Topic Test - Logic

4.4Software

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.5Programming 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

5Communication & The Internet

5.1Networks

5.1.1Benefits of Networks

5.1.2Network Performance

5.1.3Types of Network

5.1.4Client-Server Model

5.1.5Pros of Client-Server Model

5.1.6Cons of Client-Server Model

5.1.7Peer-to-Peer Model

5.1.8Pros of Peer-to-Peer Model

5.1.9Cons of Peer-to-Peer Model

5.1.10Network Hardware

5.1.11Transmission Media

5.1.12WiFi

5.1.13WiFi Frequency and Channels

5.1.14WiFi Encryption

5.1.15Network Protocols

5.1.16Transmission Protocols

5.1.17Web Protocols

5.1.18Email Protocols

5.1.19Layers

5.1.20TCP and OSI Models

5.1.21Advantages of Layering

5.1.22Topology - Star

5.1.23Topology - Mesh

5.1.24Topology - Ring

5.1.25Topology - Bus

5.1.26End of Topic Test - Networks

5.2Network 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.3The 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

6The Bigger Picture

6.1Emerging Trends, Issues & Impact

6.1.1E-Waste

6.1.2Energy Consumption

6.1.3Positive Environmental Impact

6.1.4Ethical Issues - The Digital Divide

6.1.5Ethical Issues - Net Neutrality

6.1.6Ethical Issues - Working Conditions

6.1.7Ethical Issues - Censorship

6.1.8Online Activity Tracking

6.1.9The Internet of Things

6.1.10Positive Cultural Impacts

6.1.11Negative Cultural Impacts

6.1.12Data Protection Act

6.1.13Computer Misuse Act

6.1.14Copyright Designs and Parents Act

6.1.15Creative Commons Licensing

6.1.16Freedom of Information Act

6.1.17Open Source Software

6.1.18Proprietary Software

6.1.19Licensing Issues

6.1.20End of Topic Test - Software & Issues

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