**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Lecture# Merge Sort: Divide and Conquer

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.

Login to watch the video

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Instructors (2)

Related concepts (27)

In course

Related lectures (9)

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.

Time complexity

In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.

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.

Complexity class

In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of a type of computational problem, a model of computation, and a bounded resource like time or memory. In particular, most complexity classes consist of decision problems that are solvable with a Turing machine, and are differentiated by their time or space (memory) requirements.

P (complexity)

In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. Cobham's thesis holds that P is the class of computational problems that are "efficiently solvable" or "tractable". This is inexact: in practice, some problems not known to be in P have practical solutions, and some that are in P do not, but this is a useful rule of thumb.

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, ma

Recursive Algorithms: Induction & Sorting

Explores induction, recursion, and sorting algorithms, including merge sort and the proof of correctness for recursive algorithms.

Merge Sort: Sorting Algorithm

Explains the merge sort algorithm, its correctness, and time complexity compared to other sorting algorithms.

Recursive Algorithms: Induction & Sorting

Covers induction, recursion, sorting algorithms, and the merge sort complexity in computer science.

Query Processing with Relational Operations

Covers query processing with relational operations, including query optimization and different join algorithms.