Doom makes use of a system known as Binary Space Partitioning (BSP). Binary space partitioning (BSP) is a technique used for recursively subdividing a space into convex shapes by utilizing mathematical hyperplanes. This process can take quite some time for a large level. Because of BSP, it is not possible to move the walls in the Doom Engine.
Each level is divided up into a data structure known as a Binary Tree. Each location in the Binary Tree is called a "node", where each node in the Doom Engine represents a certain area/region of the level. The root node (which is the first node at the top of the tree from which every other node originates) represents the entire level. At each branch of the tree there is a dividing line which divides the area of the node into two subnodes. This dividing line also divides linedefs into line segments called "segs".
The leaves of the tree (the bottom-most nodes with no children nodes) are convex polygons. These convex polygons are referred to as subsectors (or "SSECTORS"), and these subsectors are bound to a specific sector. Each subsector has a list of line segments (segs) associated with it.
The BSP system sorts the subsectors into the correct rendering order by using an algorithm as stated:
Begin at the root node.
Draw the child nodes of this node recursively. The child node closest to the camera is drawn first using a Scanline algorithm. The Scanline algorithm works like this according to Wikipedia: "All of the polygons to be rendered are first sorted by the top y-coordinate at which they first appear. Then each row or scan line of the image is computed using the intersection of a scanline with the polygons on the front of the sorted list. This happens while the sorted list is updated to discard no-longer-visible polygons as the current scan line progresses down the picture."
Once a subsector has been found, draw it.
The process is complete when the whole column of pixels is filled (i.e., there are no more gaps left). This ordering ensures that objects that are not visible aren't drawn or rendered; this allows maps to become very large without much performance loss!
Binary Tree Data Structure
Scan-line algorithm example retrieved from https://en.wikipedia.org/wiki/Scanline_rendering#/media/File:Scan-line_algorithm.svg