Different Ways to Efficiently Sort Large Files

Last updated: March 18, 2024

Reviewed by: Hiks Gerganov

1. Overview

Sorting large files efficiently is a common challenge in data processing and analysis. Large files often come in various formats:

  • massive log files
  • extensive datasets
  • large-scale scientific simulations

Finding optimal sorting methods is important to ensure smooth data handling and maximize resource utilization.

In this tutorial, we’ll explore different ways to tackle large files, focusing on the sort command. Furthermore, we’ll be discussing options associated with the sort command such as -u and –parallel.

In summary, we’ll also go through data generation, the option of splitting large files into smaller chunks for improved performance, and the impact of locale changes on sorting efficiency.

2. Dataset Generation

Before diving into the sorting methods, let’s set up a sizable dataset to use for all measurements.

We’ll create a large file named data.txt with millions of records. For demonstration purposes, each record will have two fields, separated by a pipe:

$ cat data.txt
James|874
Sophia|556
Ethan|291
Olivia|128
Noah|943
Ava|487
William|777
Emma|615
Liam|105
Isabella|909
...

Let’s use the cat command to go through the script that generated the dataset:

$ cat generate_data.sh
#!/bin/bash
# Generating a large dataset
generate_data() {
  for ((i=1; i<=10000000; i++)); do
    name=$(shuf -n 1 names.txt)
    score=$((RANDOM%1000+1))
    echo "$name|$score" >> data.txt
  done
}
# Call the function to generate data
generate_data
$ bash generate_data.sh

In the script, we created a function called generate_data() to generate our large dataset. In particular, this dataset holds ten million (10000000) records with names and numbers. To pick a random name in each iteration, we used the shuf command to shuffle the names from a file names.txt. Moreover, each name is assigned a score, which is a random integer. Finally, our dataset is saved to a file called data.txt.

Now, let’s use the time command to measure the execution time of a normal sort operation over this dataset:

$ time sort data.txt > sorted_data_regular.txt
real    0m6.346s
user    0m6.879s
sys     0m0.230s

Having the regular sort time measurement provides data to understand how much improvement or optimization each method adds over the default sorting approach.

Since we dump the sorted data to another file with the > redirection operator, let’s also use -c to check if any row isn’t sorted in the sorted_data_regular.txt file:

$ sort -c sorted_data_regular.txt

When there is no output, it means that all rows are sorted correctly.

We’ll use data.txt throughout the article to measure the performance of different sorting methods under similar conditions. Notably, we clear the cache and filesystem buffers before each test. Further, we’ll use the time command to measure all execution times.

3. Sorting and Removing Duplicates

The sort -u option is a powerful tool for sorting data while removing duplicates. This is particularly useful when dealing with datasets that might contain repetitive entries, and we want to obtain a unique set of records.

In the following example, we’ll utilize the time command while using the -u option on the data.txt file:

$ time sort -u data.txt > sorted_unique_data.txt
real    0m4.350s
user    0m5.649s
sys     0m0.076s

Here, we dump the sorted data to the sorted_unique_data.txt file.

Moreover, the output contains the time in seconds that it took to sort the file via sort -u. Notably, there is an improvement of around two seconds.

4. Sorting Algorithms

Choosing the right sorting algorithm can significantly impact sorting performance, depending on the data type and its distribution.

Let’s briefly see how different data types relate to certain sorting algorithms:

  • string data: algorithms like TimSort are effective in reducing comparison operations
  • integer data: QuickSort is commonly used due to its general efficiency and adaptability
  • floating-point data: MergeSort is better as it preserves the order of equal elements

Consequently, we can choose the appropriate sorting algorithm. By default, sort uses a hybrid sorting algorithm that combines QuickSort and MergeSort. Nevertheless, specifying other sorting methods isn’t directly possible with sort alone.

Still, by customizing the sorting algorithm based on the data type and distribution, we can further optimize the sorting process and achieve better performance when dealing with large files.

Additionally, using specialized sorting algorithms tailored to specific data types is a useful approach to handling diverse datasets efficiently.

5. Utilizing Multiple Threads

For exceptionally large files, sorting can become a resource-intensive operation, often taking a considerable amount of time. Because of this, the sort command offers the –parallel option, enabling us to use multiple sorting threads simultaneously.

Let’s utilize four threads to sort our data.txt file and check the performance:

$ time sort --parallel=4 data.txt > sorted_parallel_data.txt
real    0m4.037s
user    0m5.497s
sys     0m0.108s

By specifying –parallel=4, we instruct the sort command to divide the input data into multiple chunks and sort them in parallel using four threads.

The actual performance improvement obtained from using the –parallel option depends on various factors:

  • file size
  • available system resources
  • sorting algorithm

In some cases, using more threads than the number of available CPU cores might not provide any additional benefit and could even degrade performance.

Therefore, it’s important to experiment with different values and observe the performance impact on our specific system.

6. Splitting Large Files

In some scenarios, sorting an entire large file at once might not be feasible due to limited memory resources. In such cases, we split the large file into smaller batches, sort them individually, and then merge them into the final sorted file.

Built-in sort methods work well for relatively large files that can fit in memory, but manual splitting is essential for the customization of chunk size or handling irregular data distributions.

Let’s understand this approach using the split tool to break data.txt into smaller files:

$ split -l 10000 -d data.txt splitdata
splitdata0
splitdata1
splitdata2
splitdata3
..

In this example, we used the -l option to indicate that the file is split according to the provided number of lines. In addition, the -d option uses numeric suffixes starting from 0 to each of the new filenames. Thus, the command splits data.txt into smaller files, each containing 10000 lines. As we can see, the splitdata prefix is also added to the generated files.

Next, let’s sort the splitdata files:

$ for X in splidata*; do sort -t'|' -k2 -n < $X > final-$X; done

First, we initiate a loop that iterates over files with names that match the pattern splitdata*. In this case, we used several options with the sort command:

  • -t ‘ |’ specifies the delimiter used to separate fields in each line
  • -k2 specifies that the sorting should be based on the second field in each line
  • -n performs numerical sorting

Finally, the command saves the sorted output into new files with the prefix final-.

Now, let’s merge the sorted files into one large file while checking the time taken for that operation:

$ time sort -t'|' -k2 -n -m final-splitdata* > sorted_split_data.txt
real    0m4.502s
user    0m5.013s
sys     0m0.071s

To merge files, we use the -m option. All final-splitdata files are now sorted into our final file sorted_split_data.txt. Finally, we see that splitting smaller files enhances the performance, as long as we don’t take the time for the initial splitting and sorting into account.

7. Locale Changes

Another factor that can significantly affect sorting performance is the locale setting. The locale determines how characters are displayed, compared, and sorted. By default, the sort command uses the locale settings of the system.

7.1. Using en_US.utf8 Locale

First, let’s consider this example where we set the locale to en_US.utf8:

$ time LC_ALL=en_US.utf8 sort data.txt > sorted_data_en_locale.txt
real    0m5.748s
user    0m6.380s
sys     0m0.092s

In the above example, we set the value of LC_ALL to en_US.utf8 to configure the locale.

7.2. Using C Locale

One commonly used locale for sorting is C or POSIX, which provides simple and fast sorting as it doesn’t interpret complex characters.

Let’s see how this affects the sorting performance:

$ time LC_ALL=C sort data.txt > sorted_data_c_locale.txt
real 0m3.178s
user 0m4.615s
sys 0m0.080s

When comparing both performance stats, we see that using the C locale drastically enhances performance.

Notably, in our scenario, using the C locale was better and worked without issues. However, using a different non-C dataset might lead to unexpected results in terms of time and content. Also, depending on the original locale and environment, these results may vary.

8. Conclusion

In this article, we discussed various methods that can help us to sort large files more efficiently.

We looked at the sort command with several of its options. In addition, we learned how to split files, sort, and merge them. Furthermore, we understood the importance of setting the locale in our environment when sorting.

Finally, we measured the performance of each method across the same dataset.

Comments are open for 30 days after publishing a post. For any issues past this date, use the Contact form on the site.