Mergesort Algorithm Example

Study Notes

Mergesort is a sorting algorithm that divides the input data into smaller parts, sorts them recursively, and then merges them into a single sorted list.
The merging process involves comparing elements from two sorted arrays and combining them into a single sorted array.
The algorithm continues until all parts are merged into a single sorted list.

The mergesort algorithm takes three parameters: data, firstItem, and lastItem.
If firstItem is less than lastItem, the algorithm divides the data into two halves, recursively sorts each half, and then merges the two sorted halves.

Quicksort is a fast sorting algorithm with an average running time of O(N log N) and a worst-case running time of O(N2).
The algorithm works by selecting a pivot element, partitioning the list around the pivot, and then recursively sorting the sublists.
The heap property ensures that the smallest element is stored in the root of the tree.

A priority queue is a data structure that follows the heap-order property, where the parent node is either greater than or equal to its child nodes.
Basic heap operations include inserting an element, deleting an element, and finding the minimum element.
Inserting an element involves adding it to the end of the tree, moving the parent value into the empty slot, and bubbling the hole up until the parent is less than or equal to the new element.
Deleting an element involves finding the minimum element, removing it, and then bubbling the hole down until the last element can be placed in the empty slot.

Sorting is the process of arranging a group of items into a defined order based on a particular criteria.
External sorting algorithms are designed to handle very large inputs that cannot fit into memory.
External sorting algorithms involve reading the input data from a file, sorting it into smaller chunks, and then merging the sorted chunks into a single sorted file.

An example of external sorting is the Mergesort algorithm, which involves reading the input data, sorting it into smaller chunks, and then merging the sorted chunks into a single sorted file.
A program in C++ can be used to illustrate the working of the algorithm.

A graph consists of nodes (vertices) and connections between them (edges).
Graphs can be directed or undirected, and edges can be weighted or unweighted.
Different types of graphs include directed graphs, undirected graphs, and weighted graphs.

Greedy algorithms involve making the locally optimal choice at each step, hoping to find a global optimum solution.
Examples of greedy algorithms include coin-changing, scheduling, and Huffman coding.
Coin-changing involves making the exact change with the minimum number of coins, using the largest coin possible.
Scheduling involves finding the best way to schedule jobs in order to minimize the average completion time.

Huffman coding is a method of encoding data using a variable-length prefix code.
The algorithm works by building a Huffman tree, where each leaf node represents a character, and the weight of each node is the sum of the frequencies of its leaves.
The algorithm involves selecting the two trees of smallest weight, breaking ties arbitrarily, and forming a new tree with the two subtrees.

Divide and Conquer algorithms involve dividing a problem into smaller subproblems, solving each subproblem recursively, and then combining the solutions to the subproblems to form the solution to the original problem.
The algorithm consists of two parts: divide and conquer.