Insertion & Merge Sort

Test yourself

Insertion Sort

Insertion sort is a simple sorting algorithm, which is very intuitive.

The concept

Imagine sorting a deck of cards.
Hold the deck of cards in one hand, and place a single card down on the desk.
Take a card from the top of the deck in your hand, and put it in the correct place in the other deck.
Repeat until all the cards are gone.

In English

Take the second card:
- Compare to the first card, swap if needed.
Take the third card:
- Compare to second card, swap if needed.
- Compare to first card, swap if needed.
Take the fourth card:
- Compare to all previous cards.
Repeat for all cards.

In pseudocode

Pros and cons of insertion sort

Pros:
- Easy to implement.
- Little memory used.
Cons:
- Not very efficient.

Merge Sort

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

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

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:
- A very efficient algorithm.
Cons:
- Can be slower for small lists.
- Needs additional memory.

1Components of a Computer

1.1Structure & Function of the Processor

1.1.1Structure of the CPU

1.1.2Fetch, Decode, Execute Cycle

1.1.3Factors Affecting CPU Performance

1.1.4CPU Architecture

1.2Types of Processors

1.2.1CISC & RISC

1.2.2Multicore & Parallel Cores

1.3Input, Output & Storage

1.3.1Computer Systems

1.3.2Magnetic Storage

1.3.3Optical Storage

1.3.4Types of Optical Storage

1.3.5Types of Memory

1.3.6Flash Memory

1.3.7Virtual Memory

2Software & Software Development

3Exchanging Data

4Data Types, Data Structures & Algorithms

4.1Data Types

4.1.1Data Types

4.1.2Arrays & Strings

4.1.3Representing Numbers

4.1.4Binary Arithmetic

4.1.5Hexadecimal

4.1.6Converting Binary Numbers

4.1.7Floating Points in Binary

4.1.8Floating Point Arithmetic

4.1.9Bitwise Manipulation

4.1.10Character Sets

4.2Data Structures

4.2.1Arrays, Linked Lists & Queues

4.2.2Graphs, Hash Tables & Stacks

4.2.3Trees

4.3Boolean Algebra

4.3.1Computational Logic

4.3.2Boolean Logic

4.3.3Karnaugh Maps

4.3.4Boolean Identities

4.3.5Flip Flops & Adder Circuits

5Legal, Moral, Cultural & Ethical Issues

5.1Computing Related Legislation

5.1.1Data Protection Act (1998)

5.1.2Computer Misuse Act (1990)

5.1.3Copyright Designs and Patents Act (1988)

5.1.4Regulation of Investigatory Powers Act (2000)

5.2Moral & Ethical Issues

5.2.1Online Activity Tracking

5.2.2Censorship

5.2.3Cultural Issues

5.2.4Environmental Issues

5.2.5Layout, Colour Paradigms & Character Sets

6Elements of Computational Thinking

6.1Thinking Abstractly

6.1.1Abstraction

6.2Thinking Procedurally

6.2.1Decomposition

6.3Thinking Logically

6.3.1Pseudocode & Flow Diagrams

7Problem Solving & Programming

7.1Programming Techniques

7.1.1Programming Fundamentals

7.1.2Modularity

7.2Programming Construction

7.2.1Integrated Development Environments

7.2.2Testing

8Algorithms

8.1Algorithms

8.1.1Interpreting, Correcting & Completing Algorithm

8.1.2Sort Algorithms

8.1.3Insertion & Merge Sort

8.1.4Search Algorithms

Jump to other topics