8.1.3
Insertion & Merge Sort
Insertion Sort
Insertion Sort
Insertion sort is a simple sorting algorithm, which is very intuitive.


The concept
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
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.


Pros and cons of insertion sort
Pros and cons of insertion sort
- Pros:
- Easy to implement.
- Little memory used.
- Cons:
- Not very efficient.
Merge Sort
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.
1Components of a Computer
1.1Structure & Function of the Processor
1.2Types of Processors
2Software & Software Development
2.1Systems Software
2.2Applications Generation
2.3Software Development
3Exchanging Data
3.1Compression, Encryption & Hashing
3.3Networks
4Data Types, Data Structures & Algorithms
4.1Data Types
5Legal, Moral, Cultural & Ethical Issues
5.1Computing Related Legislation
6Elements of Computational Thinking
6.1Thinking Abstractly
6.2Thinking Procedurally
6.3Thinking Logically
7Problem Solving & Programming
7.1Programming Techniques
7.2Programming Construction
Jump to other topics
1Components of a Computer
1.1Structure & Function of the Processor
1.2Types of Processors
2Software & Software Development
2.1Systems Software
2.2Applications Generation
2.3Software Development
3Exchanging Data
3.1Compression, Encryption & Hashing
3.3Networks
4Data Types, Data Structures & Algorithms
4.1Data Types
5Legal, Moral, Cultural & Ethical Issues
5.1Computing Related Legislation
6Elements of Computational Thinking
6.1Thinking Abstractly
6.2Thinking Procedurally
6.3Thinking Logically
7Problem Solving & Programming
7.1Programming Techniques
7.2Programming Construction

Unlock your full potential with GoStudent tutoring
Affordable 1:1 tutoring from the comfort of your home
Tutors are matched to your specific learning needs
30+ school subjects covered