Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Merge Sort: Divide and Conquer

In course

CS-250: Algorithms I

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, major algorithmic paradigms such as dynamic programming, s ...

Description

This lecture covers the Divide and Conquer approach applied to sorting, focusing on the Merge Sort algorithm. It explains the process of dividing an array into subarrays, recursively sorting them, and then merging them back together to produce a single sorted array. The instructor demonstrates the Merge procedure, simplification techniques for implementation, and the analysis of divide-and-conquer algorithms. The lecture concludes with a detailed analysis of the Merge Sort algorithm's time complexity, showing that it runs in O(nlog n) time, making it much faster than Insertion sort for large instances.

Instructors (3)

Alessandro Chiesa

Alessandro Chiesa is a faculty member in computer science. He conducts research in complexity theory, cryptography, and security, with a focus on the theoretical foundations and practical implementations of cryptographic proofs that are short and easy to verify. He is a co-author of several zkSNARK libraries, and is a co-inventor of the Zerocash protocol. He has co-founded Zcash and StarkWare Industries. He is a recipient of a Sloan Research Fellowship (2021), an Okawa Foundation Research Grant (2020), and Google Faculty Research Awards (2018 and 2017). He was included in MIT Technology Review's "35 Innovators Under 35" list in 2018.

Mikhail Kapralov

Ola Nils Anders Svensson

Official source

Ontological neighbourhood

Theoretical computer science

Algorithms and data structures: Analysis of algorithms

Related concepts (29)

Sorting algorithm

In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. Efficient sorting is important for optimizing the efficiency of other algorithms (such as search and merge algorithms) that require input data to be in sorted lists. Sorting is also often useful for canonicalizing data and for producing human-readable output.

Merge sort

In computer science, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the relative order of equal elements is the same in the input and output. Merge sort is a divide-and-conquer algorithm that was invented by John von Neumann in 1945. A detailed description and analysis of bottom-up merge sort appeared in a report by Goldstine and von Neumann as early as 1948.

External sorting

External sorting is a class of sorting algorithms that can handle massive amounts of data. External sorting is required when the data being sorted do not fit into the main memory of a computing device (usually RAM) and instead they must reside in the slower external memory, usually a disk drive. Thus, external sorting algorithms are external memory algorithms and thus applicable in the external memory model of computation. External sorting algorithms generally fall into two types, distribution sorting, which resembles quicksort, and external merge sort, which resembles merge sort.

Bubble sort

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the input list element by element, comparing the current element with the one after it, swapping their values if needed. These passes through the list are repeated until no swaps had to be performed during a pass, meaning that the list has become fully sorted. The algorithm, which is a comparison sort, is named for the way the larger elements "bubble" up to the top of the list.

Merge algorithm

Merge algorithms are a family of algorithms that take multiple sorted lists as input and produce a single list as output, containing all the elements of the inputs lists in sorted order. These algorithms are used as subroutines in various sorting algorithms, most famously merge sort. The merge algorithm plays a critical role in the merge sort algorithm, a comparison-based sorting algorithm.

Related lectures (47)

Sorting Algorithms: Selection and Insertion

Introduces selection and insertion sorting algorithms, explaining their correctness and time complexity.

Dynamic Programming: Palindromic Subsequences

Explores dynamic programming for palindromic subsequences, merging binary search trees, and finding the median of two sorted arrays.

Recursive Sorting: Merge Sort

Explains recursive sorting using Merge Sort and its linearithmic complexity.

Algorithmic Challenges: Solutions and Optimization

Explores algorithmic challenges, time complexity, optimization, recursion, and probability calculations.

Hashing and Quick Sort