Medium Algorithms

Merge sort is a divide and conquer algorithm that divides the input array into two halves, recursively sorts them, and then merges the sorted halves. With a consistent O(n log n) time complexity regardless of input data, it outperforms simpler algorithms on large datasets. While requiring O(n) auxiliary space for the merging process, it guarantees stability and is particularly efficient for linked lists. Merge sort is often used in external sorting when data doesn't fit in memory.

Quick sort is a divide and conquer algorithm that picks an element as a pivot and partitions the array around the pivot. With an average time complexity of O(n log n) and minimal space requirements, it's typically faster in practice than other O(n log n) algorithms like merge sort. However, it has a worst-case time complexity of O(n²) with poor pivot selection and is not stable. Quick sort is widely used and serves as the foundation for many programming language sorting implementations.

Binary search finds the position of a target value within a sorted array by repeatedly dividing the search interval in half. With a logarithmic time complexity of O(log n), it's dramatically more efficient than linear search for large datasets. Binary search requires the array to be sorted beforehand, making it ideal for situations where searching occurs frequently on relatively static data. This algorithm is the foundation for many efficient data structures like binary search trees and is widely used in database systems, dictionaries, and numerous programming applications.

Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It uses a stack data structure (often implemented using recursion) to keep track of vertices to visit next. DFS has applications in topological sorting, finding connected components, solving mazes, and detecting cycles in graphs.

Breadth-First Search (BFS) is a graph traversal algorithm that explores all vertices at the present depth level before moving on to vertices at the next depth level. It uses a queue to keep track of the next vertices to visit, ensuring that vertices are visited in order of their distance from the source vertex. BFS is commonly used for finding the shortest path in unweighted graphs, connected components, and solving puzzles with the fewest possible moves.

Topological Sort is an algorithm for ordering the vertices of a directed acyclic graph (DAG) such that for every directed edge (u,v), vertex u comes before vertex v in the ordering. This algorithm is essential for scheduling tasks with dependencies, course prerequisites planning, and compilation sequence determination. A graph must have no directed cycles to have a valid topological ordering, making this algorithm a useful tool for cycle detection as well.

Prim's algorithm builds a minimum spanning tree (MST) by starting at an arbitrary vertex and repeatedly adding the cheapest edge that connects the existing tree to a vertex outside it. Each step strictly grows the tree by one vertex until every vertex is included. The greedy choice is provably optimal because of the cut property of MSTs. Common applications include network design, clustering, and approximation algorithms for the traveling salesman problem.

Kruskal's algorithm builds a minimum spanning tree (MST) by sorting all edges by weight and adding them one at a time, skipping any edge that would form a cycle. A disjoint-set (union-find) data structure makes the cycle check efficient. Unlike Prim's, Kruskal's grows the tree as a forest of components that gradually merge, making it well-suited to sparse graphs. It's used in network design, image segmentation, and as a building block for clustering algorithms.

A binary search tree (BST) maintains the invariant that every node's left subtree contains only smaller values and its right subtree only larger values. Inserting a value walks the tree from the root, branching left or right at each node by comparison, until it reaches a missing child where the new node is attached. Average insertion is O(log n) when the tree is balanced; the worst case degrades to O(n) when input order produces a skewed tree, motivating self-balancing variants like AVL and red-black trees.

A binary min-heap is a complete binary tree where every parent is less than or equal to its children. Stored as an array, the children of index i live at 2i+1 and 2i+2, so the structure stays compact without explicit pointers. Each insertion appends the new value at the end and 'sifts up' — repeatedly swapping it with its parent while the parent is larger — restoring the heap property in O(log n). Heaps are the backbone of priority queues, heap sort, and shortest-path algorithms like Dijkstra's.

The longest common subsequence (LCS) of two sequences is the longest sequence appearing in both as a subsequence — preserving order but not contiguity. The standard dynamic-programming solution fills an (m+1)×(n+1) table where dp[i][j] is the LCS length of the first i and j characters. When characters match, the cell extends the diagonal by one; otherwise it inherits the larger of its top and left neighbours. The table fills in O(m·n), and a traceback recovers the actual subsequence. LCS is the workhorse behind Unix `diff`, version control merge, and computational biology sequence alignment.

A* finds the shortest path from a start cell to a goal cell on a grid by combining the cost so far (g) with an admissible estimate of the remaining cost (h, here Manhattan distance). It always expands the open-set node with the smallest f = g + h, which lets it focus exploration toward the goal rather than fanning out uniformly like Dijkstra's. With an admissible, consistent heuristic, A* is guaranteed to return an optimal path, and it routinely outperforms uninformed search on spatial maps. Pathfinding in games, robotics, and routing systems is the canonical application.

Dijkstra's algorithm specialised to a grid finds the shortest path from a start cell to a goal cell when every step costs the same. It expands the open-set node with the smallest tentative distance, relaxing each unblocked neighbour, until it pops the goal. Unlike A*, it has no heuristic — every direction is treated equally — so it explores the frontier as an expanding ring around the start. The grid version makes the difference from heuristic-guided search tangible: side-by-side with A*, you see exactly how much exploration the heuristic saves.

The recursive backtracker — also called randomised depth-first search — generates a perfect maze (one with exactly one path between any two cells) by carving passages from a starting cell. At each step it picks a random unvisited neighbour two cells away, knocks down the wall between them, and recurses; when no unvisited neighbours remain, it backtracks. The result is a long, winding maze with few short branches, distinct from algorithms like Prim's or Wilson's that produce more uniform structure. Mazes generated this way are a common test bed for pathfinding algorithms.