Understanding Row Major Order

What Is Row-Major Order?

Row-major order is one of the two fundamental strategies for serialising a multi-dimensional array — that is, for flattening its logical table structure into the single linear strip of memory that hardware actually provides.

The rule is beautifully simple:

Store every element of a row together, then move to the next row.

Languages like C, C++, Objective-C, Python, Java, and Go all store their multi-dimensional arrays this way. If you’ve ever written a nested loop over a 2D array, you’ve already relied on row-major order without knowing it.

Generic Representation in Memory

Let’s make this concrete. Take a 3×4 array (3 rows, 4 columns). Logically it looks like a table:

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
block-beta
  columns 4
  A["[0][0]"] B["[0][1]"] C["[0][2]"] D["[0][3]"]
  E["[1][0]"] F["[1][1]"] G["[1][2]"] H["[1][3]"]
  I["[2][0]"] J["[2][1]"] K["[2][2]"] L["[2][3]"]

The logical 2D view — 3 rows, 4 columns, 12 elements.

In memory there are no rows or columns — only one long ribbon of slots. Row-major order places these elements into that ribbon one full row at a time:

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart LR
  subgraph R0["Row 0"]
    A["[0][0]"] --- B["[0][1]"] --- C["[0][2]"] --- D["[0][3]"]
  end
  subgraph R1["Row 1"]
    E["[1][0]"] --- F["[1][1]"] --- G["[1][2]"] --- H["[1][3]"]
  end
  subgraph R2["Row 2"]
    I["[2][0]"] --- J["[2][1]"] --- K["[2][2]"] --- L["[2][3]"]
  end
  D --> E
  H --> I

Generic representation of a two-dimensional array in row-major order in memory — Row 0 is placed first, Row 1 immediately after, then Row 2. Rows sit back-to-back.

Think of reading a book — you finish the first line completely before starting the second. That’s exactly row-major order.

Layout in Memory — The N-Dimensional Case

The concept scales cleanly to any number of dimensions. Consider a general N-dimensional array with sizes:

Dn × Dn-1 × Dn-2 × ... × D1

where D1 is the innermost (lowest) dimension and Dn is the outermost (highest) dimension.

Row-major order serialises this array by a single governing rule:

The lowest dimension index moves the fastest. The highest dimension index moves the slowest.

Think of it like an odometer. The rightmost digit (lowest dimension) ticks up on every step. The digits to the left (higher dimensions) only increment when the ones to their right overflow.

For a 3 × 4 array (D2=3, D1=4), the indices progress like this:

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart LR
  subgraph slow["Outer index I₂ — moves slowly (row)"]
    direction TB
    R0["I₂ = 0"] ~~~ R1["I₂ = 1"] ~~~ R2["I₂ = 2"]
  end
  subgraph fast["Inner index I₁ — moves fast (column)"]
    direction LR
    C00["I₁=0"] --> C01["I₁=1"] --> C02["I₁=2"] --> C03["I₁=3"]
    C10["I₁=0"] --> C11["I₁=1"] --> C12["I₁=2"] --> C13["I₁=3"]
    C20["I₁=0"] --> C21["I₁=1"] --> C22["I₁=2"] --> C23["I₁=3"]
  end
  R0 -->|"walks"| C00
  C03 -->|"reset, I₂ increments"| R1
  R1 -->|"walks"| C10
  C13 -->|"reset, I₂ increments"| R2
  R2 -->|"walks"| C20

Row major order lays out elements by moving the lowest dimension the fastest — I₁ (column) races through 0→1→2→3, then I₂ (row) increments by one.

The memory ribbon therefore fills up in this exact sequence:

[0][0]  [0][1]  [0][2]  [0][3]  [1][0]  [1][1]  [1][2]  [1][3]  [2][0]  [2][1]  [2][2]  [2][3]
  ↑ I₁ sprints across →          ↑ I₁ sprints across →           ↑ I₁ sprints across →

You can verify this yourself — run the code below and watch the order elements are visited:

arr = [
    [10, 20, 30, 40],  # Row 0
    [50, 60, 70, 80],  # Row 1
    [90, 11, 12, 13],  # Row 2
]

print("Row-major traversal order:")
for i in range(3):          # outer: row — moves slowly
    for j in range(4):      # inner: column — moves fastest
        print(f"arr[{i}][{j}] = {arr[i][j]}")

Accessing Elements — The Address Formula

Now that you know the layout, let’s derive how the CPU computes the memory address of any element.

Building the Formula

For an N-dimensional array Dn × Dn-1 × ... × D1 with an element at index (In, In-1, ..., I1):

To reach a specific element, you skip over:

• In complete “slabs” of size Dn-1 × Dn-2 × ... × D1
• In-1 complete “slices” of size Dn-2 × ... × D1
• … and so on, down to I1 individual elements

The full offset (in number of elements from the start):

offset = In × (Dn-1 × Dn-2 × ... × D1)
       + In-1 × (Dn-2 × ... × D1)
       + ...
       + I2 × D1
       + I1

The memory address is then:

address = base_address + offset × element_size

For a 2D Array

For the common 2D case (N=2), dimensions D2 × D1 (rows × cols), element at (i, j):

offset  = i × D1 + j
        = i × num_cols + j

address = base_address + (i × num_cols + j) × element_size

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  Goal["Find address of arr[I₂][I₁]<br/>in an array of size D₂ × D₁"]
  S1["Skip I₂ complete rows<br/>I₂ × D₁ elements"]
  S2["Walk I₁ steps into that row<br/>+ I₁ elements"]
  Off["offset = I₂ × D₁ + I₁"]
  Addr["address = base + offset × element_size"]

  Goal --> S1 --> S2 --> Off --> Addr

Calculating the base address of the value at (I₂, I₁) — skip whole rows, then step into the target row.

Worked Example

3×4 array, base_address = 1000, element_size = 4 bytes. Find arr[2][1]:

offset  = 2 × 4 + 1  =  9
address = 1000 + 9 × 4  =  1036

Verify by counting: Row 0 → offsets 0–3 · Row 1 → offsets 4–7 · Row 2 → offsets 8–11. The element at [2][1] is the 2nd element (j=1) inside Row 2, which starts at offset 8. So offset = 8 + 1 = 9. ✓

# Verify the formula manually
base_address = 1000
element_size = 4
num_cols = 4   # D1

i, j = 2, 1

offset  = i * num_cols + j
address = base_address + offset * element_size

print(f"arr[{i}][{j}] is at offset {offset}, memory address {address}")
# Expected: offset = 9, address = 1036

Why the Formula Uses num_cols, Not num_rows

This trips up a lot of beginners. Why multiply by the number of columns, not the number of rows?

Mental model: The index i tells you how many complete rows to jump over. Each row contains num_cols elements. So to jump one row, you move num_cols positions forward in memory. That’s the stride.

num_rows never appears because rows tell you how many rows exist — they don’t tell you how wide each row is. The width (stride) is always num_cols.

If you accidentally used num_rows = 3 in our example:

offset = 2 × 3 + 1 = 7   ← WRONG

Offset 7 points to arr[1][3] = 80 — completely the wrong element.

Key Takeaways

Row-major is the reason a simple nested loop can be either blazingly fast or painfully slow. Understanding this layout is the first step toward writing cache-efficient code — which you’ll explore in the traversal lessons ahead.