In this video I describe in detail how my implementation of the KWay External Merge Sort algorithm works. KWay External Merge Sort is an algorithm used to sort large datasets that don't fit in main memory (usually RAM). Therefore, this algorithm is used by databases like Postgres to process ORDER BY queries when tables don't fit in memory. The algorithm consists of a series of "passes" through one or multiple files and a number of inmemory buffers used to load and process different chunks of a file in each pass. The end result is a file that contains all the requested rows sorted by the keys given in the ORDER BY clause.
LINKS
Algorithm Implementation:
https://github.com/antoniosarosi/mkdb...
✉ CONTACT INFO
Business Email: [email protected]
Contact Email: [email protected]
Twitter: / antoniosarosi
Instagram: / antoniosarosi
LinkedIn: / antoniosarosi
MUSIC
• [Chillstep] Broken Elegance Shelter
• Ptr. Genesis
• Digital Road
• Juno
CHAPTERS
00:00 Introduction
00:22 The Memory Problem
01:32 Database Tables & Sorting
03:18 KWay Data Structures
04:38 Algorithm Execution (Pass 0)
06:17 Pass 1
09:22 Pass 2
11:07 I/O Complexity
11:58 Variable Length Data
13:16 Final Thoughts
HASHTAGS
#programming
#computerscience
#algorithm