why in the second row, the second column is taller than the other

Question

\documentclass[]{article}
\usepackage{longtable}
\usepackage{array}
\usepackage{booktabs}
\begin{document}

    \begin{longtable}{|m{2cm}||m{1cm}|m{1.5cm}|p{3.8cm}|p{1cm}|p{1cm}|p{2cm}|}
        \hline   Cubesort & n & $  n \log n  $ & $ n \log n $ & n & Yes & Insertion    \\
        \hline  Shell sort & $ n $ & $ n \log^2 n $ or $ n^{3/2} $ & Depends on gap sequence; best known is $ n \log^2 n $ & 1 & No & Insertion  \\ \hline
    \end{longtable}

\end{document}

---

But when I add a row just like below, the third row and the the last column cannot centering when I using m:

\documentclass[]{article} \usepackage{longtable} \usepackage{array} \usepackage{booktabs} \begin{document}

\begin{longtable}{|m{2cm}||m{1cm}|m{1.5cm}|p{3.8cm}|p{1cm}|p{1cm}|p{2cm}|}
    \hline   Cubesort & n & $  n \log n  $ & $ n \log n $ & n & Yes & Insertion    \\
    \hline  Shell sort & $ n $ & $ n \log^2 n $ or $ n^{3/2} $ & Depends on gap sequence; best known is $ n \log^2 n $ & 1 & No & Insertion  \\ 
    \hline Bogosort & $ n $ & $ n \cdot n! $ & $ \infty $ & 1 & No & Random shuffling  \\\hline
\end{longtable}

\end{document}

Answer 1

m column type aligns at the middle (vertical) and you used m type in third column. That particular cell has more content that wraps in to second line. As a result the vertical center point is aligned. If you use p column for third, we get:

\documentclass[]{article}
\usepackage{longtable}
\usepackage{array}
\usepackage{booktabs}
\begin{document}

    \begin{longtable}{|m{2cm}||m{1cm}|p{1.5cm}|p{3.8cm}|p{1cm}|p{1cm}|p{2cm}|}
        \hline   Cubesort & n & $  n \log n  $ & $ n \log n $ & n & Yes & Insertion    \\
        \hline  Shell sort & $ n $ & $ n \log² n $ or $ n^{3/2} $ & Depends on gap sequence; best known is $ n \log² n $ & 1 & No & Insertion  \\ \hline
    \end{longtable}

\end{document}

Answer 2

m does not mean centre vertically in the space finally allocated to the cell, it means "put the reference point of the contents in its vertical centre. l',c,rcolumns (that you do not have here) have their reference point on their baseline.pcolumns have their reference point on the baseline of their top row, and if you had abcolumn its reference point would be on the baseline of its bottom row.

TeX then aligns all the boxes on the reference point leading to the green lines below. Note that the line goes through the centre of the content of the m entry.

In the one line case it is not so obvious as the line is not through the centre of the lower case n every entry has an invisible "strut" so that its position is not affected by ascenders or tall capitals, so the one line entry has its reference point essentially as if it is on the vertical centre of Ayn which is very close to the baseline, just a bit above as the strut has more height than depth.