Introduction to Merge Sort

Estimated Time

1 hour

Introduction

Introduction video

Prerequisites of the Experiment

This experiment requires you to have basic knowledge about :

And above all, a curiosity to learn and explore..!

Overview of the Experiment

  • The aim of this experiment is to understand the Merge Sort algorithm, its time and space complexity, and how it compares against other sorting algorithms.
  • The experiment features a series of modules with video lectures, interactive demonstrations, simulations, hands-on practice exercises and quizzes to self analyze.

Learning Objectives of the Experiment

In this experiment, you will be able to do the following:

  • Learn about the divide and conquer strategy and how it can be used to solve the sorting problem.
  • Given an unsorted array of numbers, generate a sorted array of numbers by applying Merge Sort
  • Understand MergeSort operations : splitting and merging, also the associated time complexity through interactive animations.
  • Demonstrate knowledge of time complexity of Merge Sort by counting the number of operations involved in splitting the array at each level and then merging in sorted order.
  • Compare Merge Sort with other sorting algorithms and realise mergesort as a stable comparison sorting algorithm.

Experiment Modules & their Weightage

Module Weightage Expectation
Pre-test 10% Solve All Questions
Split 20% Practice how to recursively split arrays
Merge 20% Practice how to merge sorted arrays
Mergesort 30% Practice the full algorithm
Post-test 20% Solve all Questions

Pre-test of the Experiment

Estimated Time

10 minutes

Instructions for Pre-Test

  • Pretest includes questions on sorting, binary trees and logarithms.
  • If you want to revise these topics before taking the quiz, go through the Recap module first.
  • Read the questions in the quiz section and select the correct option from the ones provided. Please note that some questions may have more than one correct response.

Quick look at Sorting, Binary Trees and Logarithms

What is Sorting?

Given a list of random numbers, sorting means ordering the numbers in either ascending or descending order. By default, we sort numbers in an ascending order.

Unsorted and Sorted arrays

sort

What is a Binary Tree?

Trees are hierarchical data structures.

  • The topmost node is called root of the tree.
  • The elements that are directly under an element are called its children.
  • The element directly above something is called its parent.
  • In a binary tree, a given node can have at maximum 2 children.
  • Leaf nodes are those having no children.

Binary Tree


binary

Logarithm

sort

A Quiz with Multiple Choice Questions

Q1. Which of these best describes an array?

(A) A data structure that shows a hierarchical behavior

(B) Container of objects of similar types

(C) Container of objects of mixed types

(D) All of the mentioned

An array is a data structure, which can store a fixed-size collection of elements of the same data type.

Q2. Write complexity of insertion at any point on an array:

(A) O(N)

(B) O(N^2)

(C) O(NLogN)

(D) None of these

Taking a general example,inserting into the middle of an array, you have to shift all the elements after that element, so the complexity for insertion in that case is O(n). Worst case would be when you have to insert at the starting of the array,you will need to move n elements.

Q3. What does it mean when we say that an algorithm X is asymptotically more efficient than Y?

(A) X will always be a better choice for small inputs

(B) X will always be a better choice for large inputs

(C) Y will always be a better choice for small inputs

(D) X will always be a better choice for all inputs

Performance could be similar for small inputs, but definitely better for larger inputs

Q4. int a = 0, b = 0;
for (i = 0; i < N; i++) {
a = a + rand();
}
for (j = 0; j < M; j++) {
b = b + rand();
}
What is the time and space complexity for the above code?

(A) O(N * M) time, O(1) space

(B) O(N + M) time, O(N + M) space

(C) O(N + M) time, O(1) space

(D) O(N * M) time, O(N + M) space

The first loop runs for O(n) time, second loop runs for O(m). Constant extra space is used for 2 variables a and b, hence O(1) space.

The Divide and Conquer strategy

Estimated Time

15 minutes

The Divide and Conquer paradigm

Introduction video to d&c

Learning Objectives of this Module

In this module, we will learn about :

  • What does divide and conquer mean and where it can be used.
  • How difficult problems can be solved by breaking them down into smaller subproblems.
  • How sorting can be done using the Divide and Conquer strategy.

The Divide and Conquer Strategy

Divide and Conquer Strategy

Divide and Conquer

Concept

Divide and conquer is a strategy based on the idea that a given hard problem can be solved by breaking it down into smaller subproblems, which are much easier to solve. A Divide and Conquer algorithm works by recursively breaking down a problem into two or more sub-problems of similar type, until these become simple enough to be solved directly.

The solutions to the sub-problems are then combined to give a solution to the original problem. A typical Divide and Conquer algorithm solves a problem using following three steps:

  • Divide : Break the given problem into subproblems of same type.
  • Conquer : Recursively solve these subproblems
  • Combine : Appropriately combine the answers

Sorting as a Divide and Conquer problem

Can we perform Sorting using Divide and Conquer?

We can visualise sorting an array of size N as two subproblems : sorting two arrays of size N/2, and then somehow combining the two smaller sorted arrays. Sorting a smaller array will be easier than sorting the bigger array.

Recursive nature of Sorting : Sorting an array of size N can be recursively broken down into sorting two smaller arrays of N/2, and each of these smaller arrays can be broken down into even smaller arrays of size N/4 each, and so on.

Merge sort is a sorting algorithm that uses this approach. In Merge Sort we will :

  • DIVIDE : Split an array into parts recursively into half.
  • CONQUER : Sort the sub-arrays individually.
  • COMBINE : Merge the sorted sub-arrays to get a big sorted array.
Look at the image below and identify the divide steps and the combine steps.

Divide and Conquer in Sorting

dc

The Split Step

Estimated Time

10 minutes

The Split Step

The split step is described here

Learning Objectives of this Module :

In this module, we will :


  • Learn how to recursively split an unsorted array into smaller sub-problems
  • Learn how to split even and odd numbered arrays
  • http://
  • Visualise the split tree

Understanding Splitting of Arrays

Finding the MID

In this case, we will recursively split our array A into two equal or nearly equal parts.
Given an array with starting index START and ending index END, we will find the midpoint :

  • MID = (NUMBER OF ELEMENTS)/2 (if array has even number of elements)
  • MID = (NUMBER OF ELEMENTS + 1)/2 (if array has odd number of elements)

Splitting the Array

After finding the MID, we then split the array into two subarrays :

  • A1 : START to MID
  • A2 : MID+1 to END
Note that an array can have even or odd number of elements.
  • Incase of even number of elements, MID will come out to be the midpoint of START AND END, and hence the array can be divided into two equal parts of size (NUMBER OF ELEMENTS)/2.
  • Incase of odd number of elements, the array will get divided into two arrays of size (NUMBER OF ELEMENTS+1)/2 and (NUMBER OF ELEMENTS-1)/2,
Look at the images below and carefully observe how even and odd numbered arrays are being split.

Splitting an Array with Even number of elements



Even Split

Split an Array with Odd number of elements



Odd Split

Demonstration for the Split Step

Demo : Split Step

Interactive artefact where user can click on Next Step or Previous Step to understand how the array splits at different levels

Exercise for the Split Step

Exercise : Split Step

Interactive artefact where user can split the array by providing the indices where the array needs to be split at each step.

The Merge Step

Estimated Time

10 minutes

Merge Step

merge step video

Learning Objectives of this Module :

In this module, we will :


  • Learn how to merge two sorted arrays into one big sorted array
  • Visualise the merge step

Merging of two sorted Arrays

What is the Merge step?


Our objective is to merge two sorted subarrays, say array[p..q] and array[q+1..r] and have the result in array[p..r].

For this we first need to make temporary arrays and copy array[p..q] and array[q+1..r] into these temporary arrays, as we can't write over the positions in array[p..r] until we have the elements originally in array[p..q] and array[q+1..r] safely copied.

Let's say we denote the temporary arrays by Subarray1[] and Subarray2[] and copy all the elements in array [p..q] into Subarray1, and all the elements in array[q+1..r] into Subarray2.

The next immediate question is how big should Subarray1 and Subarray2 be?

  • The subarray array [p..q] contains q-p+1 elements, hence Subarray1 holds q-p+1 elements.
  • The subarray array [q+1..r] contains r-q elements, hence Subarray2 holds r-q elements

Initial state



Initial state

Final State



Final State

How do we perform the merge process?


Now in order to merge the arrays, we assign pointers to the starting index of all the three arrays: Pointer1, Pointer2 and Pointer3

  • We iterate over the merged array and and at each step we pick the smaller element among the ones pointed by Pointer1 and Pointer2.
  • We add the smaller element to the merged array (considering ascending order).
  • The selected subarray pointer and merged array pointer is incremented by one at each step.
  • We continue this process until elements from both the arrays have been merged into the final array.
  • If one of the subarray pointers reaches the end, the remaining elements from the other array are just copied into the merged array.
  • In the example shown above, the merge process is at an intermediate step. Currently Pointer1 points to 48 and Pointer2 points to 65. As Pointer1 points to the lesser element (48 < 65), that number is selected and added to the merged array. Finally, both Pointer1 and Pointer 3 are moved one step ahead as shown in the figure.

Demonstration for the Merge Step

Demo : Merge Step

Interactive artefact where user can click on Next Step or Reset to understand how the arrays merge at different levels.

Exercise for the Merge Step

Exercise : Merge Step

Interactive artefact where user can split the array by providing the indices where the array needs to be split at each step

The Merge Sort Algorithm

Estimated Time

10 minutes

The Mergesort Algorithm

mergesort video

Learning Objectives of this Module :

In this module, we will :


  • Learn the merge sort algorithm
  • Visualise the merge sort tree
  • Learn how to combine the split and merge step

Merge Sort Algorithm

The Mergesort Algorithm

The merge sort algorithm combines the split and merge step, to give us a sorted array.
  • First, we keep splitting the array recursively, till we get all subarrays of size 1. Recall how we practiced this in the Split step
  • Then, once the array cannot be split further, we start tracing back on our merge sort tree
  • As we trace back, we keep merging the child subarrays and overwriting the parent subarrrays by their sorted forms.
To get a better overview of how mergesort works, look at the video below and then play around with the demo artefact to gain more clarity!

Merge Sort Tree

MS levels

Merge Sort Video

Merge sort animation

Demonstration for Merge Sort Algorithm

Demo : Merge Sort

Tree representation of the whole process

Exercise for Merge Sort

Exercise : Mergesort

Interactive artefact where user can practise mergesort

Analysis of Merge Sort

Estimated Time

20 minutes

Analysis of mergesort

time complexity is explained

Learning Objectives of this Module

In this module, we will be learning about :

  • Time and Space Complexity : We will learn about the running time of the split step, merge step and number of split and merge steps required to complete the sorting process.
  • Stable sort and Comparison sort : We will learn about what stable and comparison sorts are. Then we will see how merge sort is a stable comparison sort.
  • Applications : We will compare merge sort with other sorting algorithms and see in which situations merge sort is the optimal approach to take.

Time and Space Complexity of Merge Sort

Running Time of Merge Sort

Lets assume that we are sorting n elements of a given array.

  • The split step, takes constant time, regardless of the subarray size, as this step just computes the midpoint of the array. We indicate constant time by Θ(1).
  • The merge step merges a total of n elements, taking Θ(n) time.
  • To make things more concrete, let's say that the split and merge steps together take cn time for some constant c.

Merging at different levels

MS levels

Understanding the Merge Sort Tree

  • We have seen that merging an array of size N takes time cN.
  • For array of size N/2, merging will be of order cN/2. For size N/x, merging will be of order cN/x.
  • From the image, we can observe that at level L, we have L arrays of size N/L, and hence total merging time is L * c(N/L) = cN for each level.

Understanding Log(N) levels



MS levels

Understanding the Log(N) levels

The total time for mergesort is the sum of the merging times for all the levels. If there are L levels in the tree, then the total merging time is L * cN.

So what is L? We start with subproblems of size N and repeatedly halve until we get down to subproblems of size 1.

  • If N = 2K at level 0, then at level 1, each array is of size 2^(K-1). At level 2, each array is of size 2K-2 and at level l, each array is of size 2K-l.
  • This implies that at the last level, since size of each array is 1, 2K-L = 1.
  • This implies that (K-L) = 0. Hence, total levels (L) in the merge sort tree is K. And since N = 2K, K = log2(N).
  • Total running time of merge sort is Θ(Nlog2N).

Space Complexity of Merge Sort

While merging two arrays, we require an auxillary space to temporarily store the merged array, before we plug this partially sorted array into the main array. Hence space complexity of Merge Sort is O(N), as we require an auxillary array as big as the main input array.

Stable sort and Comparison sort

What is a Comparison Sort Algorithm?

A Comparison Sort is a sorting algorithm where the final order is determined only by comparisons between the input elements.

In Merge Sort, the merge procedure chooses an item from one of two arrays after comparing the top items from both arrays.
Hence we can say that Merge Sort is a Comparison Sort algorithm.

What is a Stable Sort Algorithm?

A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input unsorted array. For example, look at the picture below. The unsorted array has two elements with value 23. Note the order of both these elements in the stable and unstable sorted arrays.

Stable and Unstable sort



Divide and Conquer

Is Merge Sort stable?

Yes, merge sort is a stable sorting algorithm. Look at the picture below and keep and eye out for the ordering of 23 and 23*. Note how the original order of these elements is retained throughout the sorting process. The relative positioning of 23 and 23* does not change in the sorted output.

Stability of Mergesort

Stable mergesort

Comparison with other algorithms

Comparison of algorithms

comparison

Comparison with other sorting algorithms

Algorithm Time Features
Sort Average Best Worst Space Stability
Bubble sort O(n2) O(n2) O(n2) Constant Stable
Modified Bubble sort O(n2) O(n) O(n2) Constant Stable
Selection Sort O(n2) O(n2) O(n2) Constant Stable
Insertion Sort O(n2) O(n) O(n2) Constant Stable
Heap Sort O(n*log(n)) O(n*log(n)) O(n*log(n)) Constant Unstable
Merge Sort O(n*log(n)) O(n*log(n)) O(n*log(n)) Depends Stable
Quicksort O(n*log(n)) O(n*log(n)) O(n2) Constant Stable

Post Test of the Experiment

Estimated Time

10 minutes

Instructions for Quiz

Post Test includes questions on entire experiment concepts. Read the questions in the quiz section and select the correct option from the ones provided. Please note that some questions may have more than one correct response.

A Quiz with Multiple Choice Questions

Q1. What are the sizes of the sub-arrays when you split an array of size 5?

(A) 1,4

(B) 2, 3

(C) Unknown sizes

(D) Insufficient information

mid=(5+1)/2=3. So array is divided after index 3 and split into two subarrays with length 3 and 2.

Q2. What is the size of the merged array when you merge two arrays of size 3 each?

(A) 3

(B) 6

(C) 7

(D) Insufficient information

Let Array A have 2 elements and Array B have 3.Consider this sequence of sending elements into the merged array: B,A,B,A,B. Number of comparisons is 4 as the last element just goes into the merged array.

Q3. What is the best case complexity of merge sort?

(A) O(n log n)

(B) O(n)

(C) O(log n)

(D) O(n2)

The merged array is simply a combination of the two subarrays.Total elements=3+3=6

Q4. Which is false for Mergesort?

(A) The algorithm is recursive

(B) The algorithm requires extra storage for a temporary copy.

(C) The invariant is that after each merge one more element is in its final position.

(D) It is not an in-place sorting algorithm.

The mergesort algorithm always has nlogn complexity irrespective of input.

Q5. Which of the following sorting algorithms has the lowest worst-case complexity?

(A) Merge Sort

(B) Bubble Sort

(C) Quick Sort

(D) Selection Sort

(E) A,C

The statement is not necessarily true in all cases.

Q6. Which of the following sorting algorithms, which has a running time that is least dependent on the initial ordering of the input?

(A) Merge Sort

(B) Insertion Sort

(C) Selection Sort

(D) Quick Sort

Rest of the sorting algorithms have O(n^2) worst case sorting complexity but mergesort remains O(nlogn) in all cases.

Q7. In a modified merge sort, the input array is splitted at a position one-third of the length(N) of the array. What is the worst case time complexity of this merge sort?

(A) N(logN base 3)

(B) N(logN base 2/3)

(C) N(logN base 1/3)

(D) N(logN base 3/2

Recurrence relation : T(N) = T(N/3) + T(2N/3) + N. Assume a tree here.n divided in to n/3 and 2n/3. n/3 is divided into n/9 and 2n/9 ( this tree goes on the left side and vanishes to 1 element) 2n/3 is divided into 2n/9 and 4n/9 ( here 4n/9 part grows even after left side has vanished) The time complexity will be based on the deepest branch of the tree. and the elements in that branch go like n/(3/2) -- n/(3/2)^2 -- n/(3/2)^3 -- ..... 1 Solving the above equation we get n * logn/log(3/2) = n logn(base 3/2). As each level requires an O(n) merge and there are logn(base 3/2) levels in the deepest branch

Feedback of the Experiment

Feedback Form of the Experiment

The experiment ends here,thanks for participating..! Please fill in the form.

Further Readings and References of the Experiment

Explore More About Mergesort