**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: Sorting Algorithm

Description

This lecture covers the merge sort algorithm, which recursively divides a list into two sublists, sorts them, and then merges them back together. The correctness of the algorithm is explained through inductive arguments and base cases. The lecture also discusses the travel time complexity of merge sort and compares it with other sorting algorithms like quicksort and insertion sort.

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.

Related concepts (125)

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.

Bucket sort

Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort, a generalization of pigeonhole sort that allows multiple keys per bucket, and is a cousin of radix sort in the most-to-least significant digit flavor. Bucket sort can be implemented with comparisons and therefore can also be considered a comparison sort algorithm.

Insertion sort

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time by comparisons. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages: Simple implementation: Jon Bentley shows a three-line C/C++ version that is five lines when optimized. Efficient for (quite) small data sets, much like other quadratic (i.e.

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.

Related lectures (624)

Sorting Algorithms: Selection and Insertion

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

Mutable and Immutable Objects

Explains the differences between mutable and immutable objects in Python and covers native container types.

Algorithmic Complexity: Travel Time Analysis

Covers control operations, algorithmic complexity, function calls, and travel time analysis.

Python Sets Operations

Covers Python sets operations, including creation, modification, and comparison, as well as set operations like union and intersection.

String Operations: Basics and Methods

Covers the basics and methods of string operations in Python, including slicing, indexing, and formatting.