Nowadays, you can directly use apt install clang-format in Debian/Ubuntu to install clang-format. However, the clang-format provided by Debian/Ubuntu is quite old. For example, the latest version of clang-format from Ubuntu 18.04 is v7 but the latest stable version is already reached v12. You can install the latest version of clang-format by following the steps below:

Step 1: Run wget -O - https://apt.llvm.org/llvm-snapshot.gpg.key|sudo apt-key add -

Step 2: Append the following content at the end of /etc/apt/sources.list based on your operating system:

• Buster (Debian 10):

  deb http://apt.llvm.org/buster/ llvm-toolchain-buster main
  deb-src http://apt.llvm.org/buster/ llvm-toolchain-buster main
  # 11 
  deb http://apt.llvm.org/buster/ llvm-toolchain-buster-11 main
  deb-src http://apt.llvm.org/buster/ llvm-toolchain-buster-11 main
  # 12 
  deb http://apt.llvm.org/buster/ llvm-toolchain-buster-12 main
  deb-src http://apt.llvm.org/buster/ llvm-toolchain-buster-12 main
  

• Bullseye (Debian 11):

  deb http://apt.llvm.org/bullseye/ llvm-toolchain-bullseye main
  deb-src http://apt.llvm.org/bullseye/ llvm-toolchain-bullseye main
  # 11 
  deb http://apt.llvm.org/bullseye/ llvm-toolchain-bullseye-11 main
  deb-src http://apt.llvm.org/bullseye/ llvm-toolchain-bullseye-11 main
  # 12 
  deb http://apt.llvm.org/bullseye/ llvm-toolchain-bullseye-12 main
  deb-src http://apt.llvm.org/bullseye/ llvm-toolchain-bullseye-12 main
  

• Xenial (Ubuntu 16.04):

  deb http://apt.llvm.org/xenial/ llvm-toolchain-xenial main
  deb-src http://apt.llvm.org/xenial/ llvm-toolchain-xenial main
  # 11
  deb http://apt.llvm.org/xenial/ llvm-toolchain-xenial-11 main
  deb-src http://apt.llvm.org/xenial/ llvm-toolchain-xenial-11 main
  # 12
  deb http://apt.llvm.org/xenial/ llvm-toolchain-xenial-12 main
  deb-src http://apt.llvm.org/xenial/ llvm-toolchain-xenial-12 main
  

• Bionic (Ubuntu 18.04):

  deb http://apt.llvm.org/bionic/ llvm-toolchain-bionic main
  deb-src http://apt.llvm.org/bionic/ llvm-toolchain-bionic main
  # 11
  deb http://apt.llvm.org/bionic/ llvm-toolchain-bionic-11 main
  deb-src http://apt.llvm.org/bionic/ llvm-toolchain-bionic-11 main
  # 12
  deb http://apt.llvm.org/bionic/ llvm-toolchain-bionic-12 main
  deb-src http://apt.llvm.org/bionic/ llvm-toolchain-bionic-12 main
  

• Focal (Ubuntu 20.04)

  deb http://apt.llvm.org/focal/ llvm-toolchain-focal main
  deb-src http://apt.llvm.org/focal/ llvm-toolchain-focal main
  # 14
  deb http://apt.llvm.org/focal/ llvm-toolchain-focal-14 main
  deb-src http://apt.llvm.org/focal/ llvm-toolchain-focal-14 main
  # 15
  deb http://apt.llvm.org/focal/ llvm-toolchain-focal-15 main
  deb-src http://apt.llvm.org/focal/ llvm-toolchain-focal-15 main
  

• Jammy (Ubuntu 22.04)

  deb http://apt.llvm.org/jammy/ llvm-toolchain-jammy main
  deb-src http://apt.llvm.org/jammy/ llvm-toolchain-jammy main
  # 14
  deb http://apt.llvm.org/jammy/ llvm-toolchain-jammy-14 main
  deb-src http://apt.llvm.org/jammy/ llvm-toolchain-jammy-14 main
  # 15
  deb http://apt.llvm.org/jammy/ llvm-toolchain-jammy-15 main
  deb-src http://apt.llvm.org/jammy/ llvm-toolchain-jammy-15 main
  

You can check https://apt.llvm.org/ if your operating system is not on this list.

Step 3: Run sudo apt update

Step 4: Run apt search clang-format and check all available versions:

$ sudo apt search clang-format
Sorting... Done
Full Text Search... Done
arcanist-clang-format-linter/stable 0.git20161021-2 all
  clang-format linter for Arcanist

clang-format/unknown 1:13.0-53~20210202214848.38 amd64
  Tool to format C/C++/Obj-C code

clang-format-11/unknown 1:11.1.0~++20210203115409+1fdec59bffc1-1~exp1~20210203230038.161 amd64
  Tool to format C/C++/Obj-C code

clang-format-12/unknown 1:12.0.0~++20210312110334+ca14f0282fce-1~exp1~20210312221110.59 amd64
  Tool to format C/C++/Obj-C code

clang-format-13/unknown 1:13~++20210315063844+b868a3edad9d-1~exp1~20210315174553.2286 amd64
  Tool to format C/C++/Obj-C code

clang-format-6.0/stable 1:6.0.1-10 amd64
  Tool to format C/C++/Obj-C code

clang-format-7/stable 1:7.0.1-8+deb10u2 amd64
  Tool to format C/C++/Obj-C code

Step 5: Use apt install to install the clang-format you want. Then you can use --version to check the installed clang-format. You can install multiple versions of clang-format in a same environment.

$ sudo apt install -y clang-format-12
$ clang-format-12 --version
Ubuntu clang-format version 12.0.0-++20210312110334+ca14f0282fce-1~exp1~20210312221110.59

$ sudo apt install -y clang-format
$ clang-format --version
Ubuntu clang-format version 13.0.0-++20210315063844+b868a3edad9d-1~exp1~20210315174553.2286

Personally I encountered this issue and solved it by installing LLVM using the Automatic installation script they mention in their apt packages page.

You may need to install a specifc version of g++ on your system, because clang++ does not come with its own set of headers. For Ubuntu 18.04, do it by invoking: sudo apt install g++-8. Please see this nice article:

Clang++ missing C++ header?